Approximating clique-width and branch-width

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

Sang-il Oum, P. D. Seymour

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

algorithmsubmodular functionmatroidrank-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)

Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width ⋮ Computing Tree Decompositions ⋮ Rank-width of random graphs ⋮ Simple monadic theories and partition width ⋮ Solving Problems on Graphs of High Rank-Width ⋮ The Rank-Width of the Square Grid ⋮ Complexity of Ising Polynomials ⋮ On powers of graphs of bounded NLC-width (clique-width) ⋮ Approximation of the Quadratic Knapsack Problem ⋮ The relative clique-width of a graph ⋮ Covering Vectors by Spaces: Regular Matroids ⋮ The rank-width of edge-coloured graphs ⋮ Transforming graph states using single-qubit operations ⋮ Boundary classes for graph problems involving non-local properties ⋮ Rank-width: algorithmic and structural results ⋮ Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs ⋮ The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor ⋮ Steiner trees for hereditary graph classes: a treewidth perspective ⋮ Finding branch-decompositions of matroids, hypergraphs, and more ⋮ An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion ⋮ Colouring square-free graphs without long induced paths. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unifying Duality Theorems for Width Parameters in Graphs and Matroids (Extended Abstract) ⋮ Between Treewidth and Clique-Width ⋮ Parameterized edge Hamiltonicity ⋮ Maximum matching width: new characterizations and a fast algorithm for dominating set ⋮ Infinitely many minimal classes of graphs of unbounded clique-width ⋮ Meta-kernelization using well-structured modulators ⋮ A SAT Approach to Clique-Width ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Regularity Equals Monadic Second-Order Definability for Quasi-trees ⋮ Algorithms for Propositional Model Counting ⋮ Classification of real Bott manifolds and acyclic digraphs ⋮ Fast exact algorithms for some connectivity problems parameterized by clique-width ⋮ Complexity and Algorithms for Well-Structured k-SAT Instances ⋮ Computing densest \(k\)-subgraph with structural parameters ⋮ Parameterized complexity of envy-free resource allocation in social networks ⋮ Bounding clique-width via perfect graphs ⋮ Graph Operations Characterizing Rank-Width and Balanced Graph Expressions ⋮ Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices ⋮ Unnamed Item ⋮ Clique-Width for Graph Classes Closed under Complementation ⋮ Unnamed Item ⋮ Obstructions for matroids of path-width at most \(k\) and graphs of linear rank-width at most \(k\) ⋮ Unnamed Item ⋮ Parameterized Complexity of Safe Set ⋮ On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs ⋮ Perfectly matched sets in graphs: parameterized and exact computation ⋮ THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES ⋮ Linear Clique‐Width for Hereditary Classes of Cographs ⋮ Obstructions for linear rank-width at most 1 ⋮ Digraphs of bounded elimination width ⋮ Finer Tight Bounds for Coloring on Clique-Width ⋮ Branch decomposition heuristics for linear matroids ⋮ Latency-bounded target set selection in social networks ⋮ Faster algorithms for vertex partitioning problems parameterized by clique-width ⋮ Bipartite entanglement in continuous variable cluster states ⋮ Vertex-minor reductions can simulate edge contractions ⋮ Line graphs of bounded clique-width ⋮ Hypertree width and related hypergraph invariants ⋮ Solving \#SAT using vertex covers ⋮ Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width ⋮ Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width ⋮ Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory ⋮ $\mathbb F$ -Rank-Width of (Edge-Colored) Graphs ⋮ Counting truth assignments of formulas of bounded tree-width or clique-width ⋮ Obstructions for Bounded Branch-depth in Matroids ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Branch-width, parse trees, and monadic second-order logic for matroids. ⋮ Distance Hereditary Graphs and the Interlace Polynomial ⋮ Linear layouts measuring neighbourhoods in graphs ⋮ Vertex disjoint paths on clique-width bounded graphs ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ Excluding a bipartite circle graph from line graphs ⋮ Bounding Clique-Width via Perfect Graphs ⋮ Computing with Tangles ⋮ VC-dimension and Erdős-Pósa property ⋮ New Results on the Complexity of the Max- and Min-Rep Problems ⋮ Unnamed Item ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes ⋮ Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ Graph Classes with Structured Neighborhoods and Algorithmic Applications ⋮ The complexity of the matching-cut problem for planar graphs and other graph classes ⋮ Boolean-Width of Graphs ⋮ Rank-width and vertex-minors ⋮ The recognizability of sets of graphs is a robust property ⋮ Digraphs of Bounded Width ⋮ Unnamed Item ⋮ Unifying the representation of symmetric crossing families and weakly partitive families ⋮ More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints ⋮ Finding Branch-Decompositions of Matroids, Hypergraphs, and More ⋮ Unnamed Item ⋮ Rank-width and Well-quasi-ordering of Skew-symmetric Matrices ⋮ Tree Pivot-Minors and Linear Rank-Width ⋮ Canonisation and Definability for Graphs of Bounded Rank Width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A decomposition theory for matroids. I: General results
• Graph minors. X: Obstructions to tree-decomposition
• \(k\)-NLC graphs and polynomial algorithms
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Edge dominating set and colorings on graphs with fixed clique-width
• Graph minors. XIII: The disjoint paths problem
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• A Linear Recognition Algorithm for Cographs
• Improved Bounds for Matroid Partition and Intersection Algorithms
• Handbook of Graph Grammars and Computing by Graph Transformation
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• On the Relationship Between Clique-Width and Treewidth
• A Parametrized Algorithm for Matroid Branch-Width
• Matrices and matroids for systems analysis

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