Exact algorithms for the maximum planar subgraph problem: New models and experiments
Autor(en): | Chimani, M. Hedtke, I. Wiedera, T. |
Herausgeber: | D'Angelo, G. | Stichwörter: | Algorithm engineering; Drawing (graphics); Formal logic, Algorithm engineering; Graph drawing; Integer linear programming; Maximum planar subgraph; Phrases maximum planar subgraph; Pseudo boolean satisfiability; Pseudo-Boolean, Integer programming | Erscheinungsdatum: | 2018 | Herausgeber: | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing | Journal: | Leibniz International Proceedings in Informatics, LIPIcs | Volumen: | 103 | Startseite: | 22:1--22:14 | Zusammenfassung: | 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. © Markus Chimani, Ivo Hedtke, and Tilo Wiedera; licensed under Creative Commons License CC-BY |
Beschreibung: | Conference of 17th Symposium on Experimental Algorithms, SEA 2018 ; Conference Date: 27 June 2018 Through 29 June 2018; Conference Code:146403 |
ISBN: | 9783959770705 | ISSN: | 18688969 | DOI: | 10.4230/LIPIcs.SEA.2018.22 | Externe URL: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85052517306&doi=10.4230%2fLIPIcs.SEA.2018.22&partnerID=40&md5=c8edfc4a746c0b7f0e4c7c2b7f3a80bd |
Show full item record