Approximating clique-width and branch-width

DOI10.1016/J.JCTB.2005.10.006zbMath1114.05022OpenAlexW2063951771WikidataQ130418939 ScholiaQ130418939MaRDI QIDQ2496203

Publication date: 12 July 2006

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2005.10.006

zbMATH Keywords

algorithm submodular function matroid rank-width

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items (only showing first 100 items - show all)

Clique-width of path powers ⋮ Characterizations for co-graphs defined by restricted NLC-width or clique-width operations ⋮ Uncountably many minimal hereditary classes of graphs of unbounded clique-width ⋮ Tree-depth and vertex-minors ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Between treewidth and clique-width ⋮ Polynomial algorithms for protein similarity search for restricted mRNA structures ⋮ Tree automata and pigeonhole classes of matroids. I ⋮ Directed width parameters on semicomplete digraphs ⋮ Model counting for CNF formulas of bounded modular treewidth ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ Complexity of \(k\)-tuple total and total \(\{k\}\)-dominations for some subclasses of bipartite graphs ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree ⋮ The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring ⋮ Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions ⋮ On quasi-planar graphs: clique-width and logical description ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ Satisfiability of acyclic and almost acyclic CNF formulas ⋮ MSOL partitioning problems on graphs of bounded treewidth and clique-width ⋮ Tight complexity bounds for FPT subgraph problems parameterized by the clique-width ⋮ A width parameter useful for chordal and co-comparability graphs ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ Colouring of graphs with Ramsey-type forbidden subgraphs ⋮ Structure and algorithms for (cap, even hole)-free graphs ⋮ Are there any good digraph width measures? ⋮ Meta-kernelization with structural parameters ⋮ Bichain graphs: geometric model and universal graphs ⋮ Tree-representation of set families and applications to combinatorial decompositions ⋮ Polynomial-time recognition of clique-width \(\leq 3\) graphs ⋮ On the model-checking of monadic second-order formulas with edge set quantifications ⋮ Decomposition width of matroids ⋮ Compact labelings for efficient first-order model-checking ⋮ Directed NLC-width ⋮ Induced minor free graphs: isomorphism and clique-width ⋮ Fast evaluation of interlace polynomials on graphs of bounded treewidth ⋮ Automata for the verification of monadic second-order graph properties ⋮ Structural parameters for scheduling with assignment restrictions ⋮ Graphs vertex-partitionable into strong cliques ⋮ Solving problems on graphs of high rank-width ⋮ Well-quasi-ordering of matrices under Schur complement and applications to directed graphs ⋮ Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis ⋮ The complexity of finding uniform sparsest cuts in various graph classes ⋮ Regular partitions of gentle graphs ⋮ Clique-width with an inactive label ⋮ Confronting intractability via parameters ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Digraph measures: Kelly decompositions, games, and orderings ⋮ The average cut-rank of graphs ⋮ Branch-depth: generalizing tree-depth of graphs ⋮ Classes of graphs with low complexity: the case of classes with bounded linear rankwidth ⋮ Refined notions of parameterized enumeration kernels with applications to matching cut enumeration ⋮ Computing the clique-width of cactus graphs ⋮ Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors ⋮ Several notions of rank-width for countable graphs ⋮ Polynomial-time algorithm for isomorphism of graphs with clique-width at most three ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm ⋮ Recent developments on graphs of bounded clique-width ⋮ \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth ⋮ On a disparity between relative cliquewidth and relative NLC-width ⋮ The rank-width of the square grid ⋮ On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width ⋮ Monadic second-order model-checking on decomposable matroids ⋮ A little statistical mechanics for the graph theorist ⋮ Rank-width and tree-width of \(H\)-minor-free graphs ⋮ Boolean-width of graphs ⋮ Computing rank-width exactly ⋮ Well-quasi-ordering versus clique-width: new results on bigenic classes ⋮ Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity ⋮ Alliances in graphs of bounded clique-width ⋮ Obstructions for bounded shrub-depth and rank-depth ⋮ Clique-width of graphs defined by one-vertex extensions ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ On \textsf{NC} algorithms for problems on bounded rank-width graphs ⋮ C-planarity testing of embedded clustered graphs with bounded dual carving-width ⋮ Recurrence relations for graph polynomials on bi-iterative families of graphs ⋮ Unavoidable vertex-minors in large prime graphs ⋮ Excluded vertex-minors for graphs of linear rank-width at most \(k\) ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width ⋮ Using decomposition-parameters for QBF: mind the prefix! ⋮ The complexity of the vertex-minor problem ⋮ Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width ⋮ Graph operations characterizing rank-width ⋮ Comparing linear width parameters for directed graphs ⋮ Colouring square-free graphs without long induced paths ⋮ New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs ⋮ Revising Johnson's table for the 21st century ⋮ Optimal centrality computations within bounded clique-width graphs ⋮ Maximum matching in almost linear time on graphs of bounded clique-width ⋮ Clique-width of full bubble model graphs ⋮ The grid theorem for vertex-minors ⋮ On the complexity of \(\{k\}\)-domination and \(k\)-tuple domination in graphs ⋮ Linear rank-width and linear clique-width of trees ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth ⋮ Rank connectivity and pivot-minors of graphs ⋮ A characterisation of clique-width through nested partitions ⋮ Clique-width and edge contraction ⋮ Conflict-free coloring: graphs of bounded clique width and intersection graphs ⋮ Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter

Cites Work

This page was built for publication: Approximating clique-width and branch-width