Comparing width parameters on graph classes
From MaRDI portal
independence numberinduced minorminimal separatorpotential maximal cliqueSPQR treetree decompositiontree-independence number
Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)
Cites work
- 32nd annual European symposium on algorithms. ESA 2024, Royal Holloway, London, United Kingdom, September 2--4, 2024
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A logic-based algorithmic meta-theorem for mim-width
- A width parameter useful for chordal and co-comparability graphs
- Achievable sets, brambles, and sparse treewidth obstructions
- Approximating clique-width and branch-width
- Approximating Pathwidth for Graphs of Small Treewidth
- Bounding the mim‐width of hereditary graph classes
- Clique-width for hereditary graph classes
- Colouring AT-free graphs
- Computing tree decompositions with small independence number
- Distance Coloring
- Distance-\(d\) independent set problems for bipartite and chordal graphs
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Excluding a bipartite circle graph from line graphs
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Fast FPT-approximation of branchwidth
- FPT algorithms for domination in sparse graphs and beyond
- Generalized Powers of Graphs and Their Algorithmic Use
- Graph classes with structured neighborhoods and algorithmic applications
- Graph minors. I. Excluding a forest
- Graph minors. V. Excluding a planar graph
- Graph minors. X: Obstructions to tree-decomposition
- Grid induced minor theorem for graphs of small degree
- Hardness of computing width parameters based on branch decompositions over the vertex set
- scientific article; zbMATH DE number 1696534 (Why is no real title available?)
- scientific article; zbMATH DE number 1303600 (Why is no real title available?)
- scientific article; zbMATH DE number 2200042 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- scientific article; zbMATH DE number 2191988 (Why is no real title available?)
- scientific article; zbMATH DE number 7829295 (Why is no real title available?)
- Induced subgraphs and path decompositions
- Induced subgraphs and tree decompositions. II: Toward walls and their line graphs in graphs of bounded degree
- Line graphs of bounded clique-width
- Lower bounds on the mim-width of some graph classes
- Maximum matching width: new characterizations and a fast algorithm for dominating set
- Mim-width. I. Induced path problems
- Mim-width. II. The feedback vertex set problem
- Mim-width. III. Graph powers and generalized distance domination problems
- Minor-matching hypertree width
- More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
- Neighbourhood complexity of graphs of bounded twin-width
- New results on maximum induced matchings in bipartite graphs and beyond
- New Width Parameters for Independent Set: One-Sided-Mim-Width and Neighbor-Depth
- On algorithmic applications of sim-width and mim-width of (H₁,H₂)-free graphs
- On powers of graphs of bounded NLC-width (clique-width)
- On the induced matching problem
- On the Relationship Between Clique-Width and Treewidth
- Ramsey-type results on singletons, co-singletons and monotone sequences in large collections of sets
- Rank-width and tree-width of \(H\)-minor-free graphs
- Rank‐width is less than or equal to branch‐width
- Rooted directed path graphs are leaf powers
- Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
- Sparsity. Graphs, structures, and algorithms
- Split permutation graphs
- The point-set embeddability problem for plane graphs
- The treewidth of line graphs
- Tree independence number. I. (Even hole, diamond, pyramid)-free graphs
- Tree-width dichotomy
- Treewidth of the line graph of a complete graph
- Treewidth versus clique number. I: Graph classes with a forbidden structure
- Treewidth versus clique number. II: Tree-independence number
- Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure
- Twin-width II: small classes
- Twin-width. I: Tractable FO model checking
- Upper bounds to the clique width of graphs
Cited in
(2)
This page was built for publication: Comparing width parameters on graph classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6976294)
