A characterisation of clique-width through nested partitions
| Autor: | Bruno Courcelle, Udi Rotics, Daniel Meister, Charis Papadopoulos, Pinar Heggernes |
|---|---|
| Přispěvatelé: | Laboratoire Bordelais de Recherche en Informatique (LaBRI), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2, Department of Informatics, University of Bergen (UIB), Theoretical Computer Science, University of Trier, Germany, Department of Computer Science [Ioannina], University of Ioannina, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Department of Informatics [Bergen] (UiB), University of Bergen (UiB), Courcelle, Bruno |
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
Vertex (graph theory)
[INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO] 0102 computer and information sciences 01 natural sciences Combinatorics Computer Science::Discrete Mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Clique-width SAT solver Discrete Mathematics and Combinatorics 0101 mathematics Algebraic number Time complexity Mathematics Discrete mathematics Applied Mathematics 010102 general mathematics [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] Decision problem Tree structure 010201 computation theory & mathematics partitions Graph operations Boolean satisfiability problem linear clique-width MathematicsofComputing_DISCRETEMATHEMATICS clique-width |
| Zdroj: | Discrete Applied Mathematics Discrete Applied Mathematics, Elsevier, 2015, 187, pp.70-81 |
| ISSN: | 0166-218X |
| Popis: | International audience; Clique-width of graphs is defined algebraically through operations on graphs with vertex labels. We characterise the clique-width in a combinatorial way by means of partitions of the vertex set, using trees of nested partitions where partitions are ordered bottom-up by refinement. We show that the correspondences in both directions, between combinatorial partition trees and algebraic terms, preserve the tree structures and that they are computable in polynomial time. We apply our characterisation to linear clique-width. And we relate our characterisation to a clique-width characterisation by Heule and Szeider that is used to reduce the clique-width decision problem to a satisfiability problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect