Approximating rank-width and clique-width quickly
From MaRDI portal
Publication:4962768
DOI10.1145/1435375.1435385zbMath1451.05231OpenAlexW2171507355MaRDI QIDQ4962768
Publication date: 5 November 2018
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1435375.1435385
Combinatorial aspects of matroids and geometric lattices (05B35) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (33)
Parameterized complexity of graph burning ⋮ Colouring diamond-free graphs ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ Rank-width: algorithmic and structural results ⋮ On quasi-planar graphs: clique-width and logical description ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts ⋮ Structure and algorithms for (cap, even hole)-free graphs ⋮ Fast exact algorithms for some connectivity problems parameterized by clique-width ⋮ Computing densest \(k\)-subgraph with structural parameters ⋮ Bounding clique-width via perfect graphs ⋮ Polynomial-time recognition of clique-width \(\leq 3\) graphs ⋮ Stability, vertex stability, and unfrozenness for special graph classes ⋮ Unnamed Item ⋮ Classifying the clique-width of \(H\)-free bipartite graphs ⋮ Unnamed Item ⋮ Parameterized Complexity of Safe Set ⋮ New plain-exponential time classes for graph homomorphism ⋮ Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis ⋮ Hardness of computing width parameters based on branch decompositions over the vertex set ⋮ How Bad is the Freedom to Flood-It? ⋮ Hardness of computing width parameters based on branch decompositions over the vertex set ⋮ Refined notions of parameterized enumeration kernels with applications to matching cut enumeration ⋮ Parameterized Complexity of Graph Burning ⋮ Parameterized algorithms for the happy set problem ⋮ Bounding Clique-Width via Perfect Graphs ⋮ On \textsf{NC} algorithms for problems on bounded rank-width graphs ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ On structural parameterizations of firefighting ⋮ On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem ⋮ Digraphs of Bounded Width ⋮ Revising Johnson's table for the 21st century ⋮ Unnamed Item
This page was built for publication: Approximating rank-width and clique-width quickly
