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

DC FieldValueLanguage
dc.contributor.authorBeyer, S.
dc.contributor.authorChimani, M.
dc.contributor.authorHedtke, I.
dc.contributor.authorKotrbčík, M.
dc.contributor.editorKulikov, A.S.
dc.contributor.editorGoldberg, A.V.
dc.date.accessioned2021-12-23T16:32:13Z-
dc.date.available2021-12-23T16:32:13Z-
dc.date.issued2016
dc.identifier.isbn9783319388502
dc.identifier.issn03029743
dc.identifier.urihttps://osnascholar.ub.uni-osnabrueck.de/handle/unios/17262-
dc.descriptionConference of 15th International Symposium on Experimental Algorithms, SEA 2016 ; Conference Date: 5 June 2016 Through 8 June 2016; Conference Code:176619
dc.description.abstractWe 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.
dc.description.sponsorshipDeutsche ForschungsgemeinschaftDeutsche Forschungsgemeinschaft,DFG,CH 897/2-1; M. Chimani—Supported by the German Research Foundation (DFG) project CH 897/2-1.;
dc.language.isoen
dc.publisherSpringer Verlag
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.subjectArtificial intelligence
dc.subjectComputer science
dc.subjectComputers, Experimental evaluation
dc.subjectInteger linear programs
dc.subjectPlanarity
dc.subjectPractical method
dc.subjectSatisfiability problems
dc.subjectSpeed up, Integer programming
dc.titleA practical method for the minimum genus of a graph: Models and experiments
dc.typeconference paper
dc.identifier.doi10.1007/978-3-319-38851-9_6
dc.identifier.scopus2-s2.0-84977498708
dc.identifier.urlhttps://www.scopus.com/inward/record.uri?eid=2-s2.0-84977498708&doi=10.1007%2f978-3-319-38851-9_6&partnerID=40&md5=721f04fb4438168a32b3852716ab7c9f
dc.description.volume9685
dc.description.startpage75
dc.description.endpage88
dcterms.isPartOf.abbreviationLect. Notes Comput. Sci.
crisitem.author.orcid0000-0002-4681-5550-
crisitem.author.netidChMa572-
Show simple item record

Page view(s)

7
Last Week
0
Last month
2
checked on May 23, 2024

Google ScholarTM

Check

Altmetric