On the boolean-width of a graph: structure and applications
In: Graph Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010
Konferenz
Zugriff:
International audience ; Boolean-width is a recently introduced graph invariant. Similar to tree-width, it measures the structural complexity of graphs. Given any graph $G$ and a decomposition of $G$ of boolean-width $k$, we give algorithms solving a large class of vertex subset and vertex partitioning problems in time $O^*(2^{O(k^2)})$. We relate the boolean-width of a graph to its branch-width and to the boolean-width of its incidence graph. For this we use a constructive proof method that also allows much simpler proofs of similar results on rank-width in [S. Oum. Rank-width is less than or equal to branch-width. \emph{Journal of Graph Theory} 57(3):239--244, 2008]. For an $n$-vertex random graph, with a uniform edge distribution, we show that almost surely its boolean-width is $\Theta(\log^2 n)$ -- setting boolean-width apart from other graph invariants -- and it is easy to find a decomposition witnessing this. Combining our results gives algorithms that on input a random graph on $n$ vertices will solve a large class of vertex subset and vertex partitioning problems in quasi-polynomial time $O^*(2^{O(\log ^4 n)})$.
Titel: |
On the boolean-width of a graph: structure and applications
|
---|---|
Autor/in / Beteiligte Person: | Adler, Isolde ; Bui-Xuan, Binh-Minh ; Rabinovich, Yuri ; Renault, Gabriel ; Telle, Jan Arne ; Vatshelle, Martin ; Department of Informatics Bergen (UiB) ; University of Bergen (UiB) ; Algorithmes, Programmes et Résolution (APR) ; Laboratoire d'Informatique de Paris 6 (LIP6) ; Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS) ; Department of Computer Science Haifa ; University of Haifa Haifa |
Link: | |
Zeitschrift: | Graph Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010 |
Veröffentlichung: | HAL CCSD ; Springer, 2010 |
Medientyp: | Konferenz |
DOI: | 10.1007/978-3-642-16926-7_16 |
Schlagwort: |
|
Sonstiges: |
|