A practical method for the minimum genus of a graph: Models and experiments

Autor(en): Beyer, S.
Chimani, M. 
Hedtke, I.
Kotrbčík, M.
Herausgeber: Kulikov, A.S.
Goldberg, A.V.
Stichwörter: Artificial intelligence; Computer science; Computers, Experimental evaluation; Integer linear programs; Planarity; Practical method; Satisfiability problems; Speed up, Integer programming
Erscheinungsdatum: 2016
Herausgeber: Springer Verlag
Journal: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen: 9685
Startseite: 75
Seitenende: 88
We consider the problem of the minimum genus of a graph, a fundamental measure of non-planarity. We propose the first formulations of this problem as an integer linear program (ILP) and as a satisfiability problem (SAT). These allow us to develop the first working implementations of general algorithms for the problem, other than exhaustive search. We investigate several different ways to speed-up and strengthen the formulations; our experimental evaluation shows that our approach performs well on small to medium-sized graphs with small genus, and compares favorably to other approaches. © Springer International Publishing Switzerland 2016.
Conference of 15th International Symposium on Experimental Algorithms, SEA 2016 ; Conference Date: 5 June 2016 Through 8 June 2016; Conference Code:176619
ISBN: 9783319388502
ISSN: 03029743
DOI: 10.1007/978-3-319-38851-9_6
Externe URL: https://www.scopus.com/inward/record.uri?eid=2-s2.0-84977498708&doi=10.1007%2f978-3-319-38851-9_6&partnerID=40&md5=721f04fb4438168a32b3852716ab7c9f

Show full item record

Page view(s)

Last Week
Last month
checked on Apr 18, 2024

Google ScholarTM