A width parameter useful for chordal and co-comparability graphs
From MaRDI portal
Publication:1680525
DOI10.1016/j.tcs.2017.09.006zbMath1380.05151arXiv1606.08087OpenAlexW2768829599MaRDI QIDQ1680525
O-joung Kwon, Torstein J. F. Strømme, Jan Arne Telle, Dong Yeap Kang
Publication date: 16 November 2017
Published in: Theoretical Computer Science, WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1606.08087
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (16)
Solving problems on generalized convex graphs via mim-width ⋮ Mim-width. I. Induced path problems ⋮ Lower bounds on the mim-width of some graph classes ⋮ On the thinness and proper thinness of a graph ⋮ Bounding the mim‐width of hereditary graph classes ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Classes of intersection digraphs with good algorithmic properties ⋮ On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs ⋮ List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Bounding the Mim-Width of Hereditary Graph Classes. ⋮ Total 2-domination of proper interval graphs ⋮ Unnamed Item ⋮ The perfect matching cut problem revisited ⋮ The perfect matching cut problem revisited ⋮ A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Graph classes with structured neighborhoods and algorithmic applications
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Graph classes and Ramsey numbers
- Parameterized complexity of generalized domination problems
- Large minors in graphs with given independence number
- Rank-width and tree-width of \(H\)-minor-free graphs
- A partial k-arboretum of graphs with bounded treewidth
- Modular decomposition and transitive orientation
- Call routing and the ratcatcher
- Weighted domination of cocomparability graphs
- Contraction obstructions for treewidth
- Lower bounds on the mim-width of some graph classes
- Approximating clique-width and branch-width
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Complete Minors and Independence Number
- Solving #SAT and MAXSAT by Dynamic Programming
- Representation of a finite graph by a set of intervals on the real line
- On Compiling CNFs into Structured Deterministic DNNFs
- Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs
- On Hadwiger's Number and the Stability Number
- Fast Parallel Algorithms for Chordal Graphs
- Dominating Sets in Chordal Graphs
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- On Satisfiability Problems with a Linear Structure
- Parameterized Algorithms
This page was built for publication: A width parameter useful for chordal and co-comparability graphs
