首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:Exact Algorithms for the Maximum Planar Subgraph Problem: New Models and Experiments
  • 作者:Markus Chimani ; Ivo Hedtke ; Tilo Wiedera
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:103
  • 页码:22:1-22:15
  • DOI:10.4230/LIPIcs.SEA.2018.22
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:Given a graph G, the NP-hard Maximum Planar Subgraph problem asks for a planar subgraph of G with the maximum number of edges. The only known non-trivial exact algorithm utilizes Kuratowski's famous planarity criterion and can be formulated as an integer linear program (ILP) or a pseudo-boolean satisfiability problem (PBS). We examine three alternative characterizations of planarity regarding their applicability to model maximum planar subgraphs. For each, we consider both ILP and PBS variants, investigate diverse formulation aspects, and evaluate their practical performance.
  • 关键词:maximum planar subgraph; integer linear programming; pseudo boolean satisfiability; graph drawing; algorithm engineering
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有