More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints
From MaRDI portal
Publication:5009336
DOI10.1137/20M1350571zbMath1475.05160arXiv1805.11275OpenAlexW3195206410MaRDI QIDQ5009336
Mamadou Moustapha Kanté, Benjamin Bergougnoux
Publication date: 20 August 2021
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1805.11275
feedback vertex setclique-widthrank-widthmim-widthconnectivity problem\(\sigma,\rho\)-domination\(d\)-neighbor equivalence
Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (6)
Solving problems on generalized convex graphs via mim-width ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ On \(d\)-stable locally checkable problems parameterized by mim-width ⋮ 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 ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
Cites Work
- Graph classes with structured neighborhoods and algorithmic applications
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- An exact algorithm for connected red-blue dominating set
- Boolean-width of graphs
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- Graph minors. X: Obstructions to tree-decomposition
- Which problems have strongly exponential complexity?
- Output-polynomial enumeration on graphs of bounded (local) linear MIM-width
- Improved methods for approximating node weighted Steiner trees and connected dominating sets.
- Upper bounds to the clique width of graphs
- Mim-width. I. Induced path problems
- Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
- Mim-width. II. The feedback vertex set problem
- Tree-coloring problems of bounded treewidth graphs
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Fast exact algorithms for some connectivity problems parameterized by clique-width
- Faster algorithms for vertex partitioning problems parameterized by clique-width
- Approximating clique-width and branch-width
- Minimum semidefinite rank of outerplanar graphs and the tree cover number
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators
- The Complexity of Coloring Circular Arcs and Chords
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
- Multiplying matrices faster than coppersmith-winograd
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized Algorithms
- Computing the largest bond of a graph
- An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width
- Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
- On the complexity of \(k\)-SAT
- Unnamed Item
- Unnamed Item
This page was built for publication: More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints
