Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
M. Heule, St. Szeider:
"A SAT Approach to Clique-Width";
Vortrag: International Conference on Theory and Applications of Satisfiability Testing (SAT),
Helsinki, Finland;
08.07.2013
- 12.07.2013; in: "Theory and Applications of Satisfiability Testing - SAT 2013",
M. Järvisalo, A. Van Gelder (Hrg.);
Springer / LNCS,
7962
(2013),
ISBN: 978-3-642-39070-8;
S. 318
- 334.
Kurzfassung englisch:
Clique-width is a graph invariant that has been widely studied in combinatorics and computer science. However, computing the clique-width of a graph is an intricate problem, the exact clique-width is not known even for very small graphs. We present a new method for computing the clique-width of graphs based on an encoding to propositional satisfiability (SAT) which is then evaluated by a SAT solver. Our encoding is based on a reformulation of clique-width in terms of partitions that utilizes an efficient encoding of cardinality constraints. Our SAT-based method is the first to discover the exact clique-width of various small graphs, including famous graphs from the literature as well as random graphs of various density. With our method we determined the smallest graphs that require a small pre-described clique-width.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-642-39071-5
Zugeordnete Projekte:
Projektleitung Stefan Szeider:
The Parameterized Complexity of Reasoning Problems
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.