Approximating clique-width and branch-width

From MaRDI portal

Publication:2496203

Jump to:navigation, search

DOI10.1016/j.jctb.2005.10.006zbMath1114.05022OpenAlexW2063951771MaRDI 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

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

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, Graphs of bounded depth‐2 rank‐brittleness, Spined categories: generalizing tree-width beyond graphs, Fair allocation algorithms for indivisible items under structured conflict constraints, Bounding the mim‐width of hereditary graph classes, Clique‐width: Harnessing the power of atoms, Monoidal Width, A class of graphs with large rankwidth, (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels, Tangle bases: Revisited, Treewidth versus clique number. II: Tree-independence number, Monoidal Width: Capturing Rank Width, Stability, vertex stability, and unfrozenness for special graph classes, Treewidth, Circle Graphs, and Circular Drawings, Locating Eigenvalues of Symmetric Matrices - A Survey, Towards compositional graph theory, Solving problems on generalized convex graphs via mim-width, On structural parameterizations of load coloring, Bounding the Mim-Width of Hereditary Graph Classes., Parameterized algorithms for the happy set problem, Clique-width and well-quasi-ordering of triangle-free graph classes, On low rank-width colorings, An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width, On the complexity of finding large odd induced subgraphs and odd colorings, Clique-width of point configurations, Node multiway cut and subset feedback vertex set on graphs of bounded mim-width, 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

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:2496203&oldid=15202239"