More applications of the d-neighbor equivalence: connectivity and acyclicity constraints
From MaRDI portal
Publication:5075752
DOI10.4230/LIPICS.ESA.2019.17MaRDI QIDQ5075752FDOQ5075752
Authors: Benjamin Bergougnoux, Mamadou Moustapha Kanté 
Publication date: 11 May 2022
Recommendations
- More applications of the \(d\)-neighbor equivalence: acyclicity and connectivity constraints
- Fast exact algorithms for some connectivity problems parameterized by clique-width
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
- Algorithmic lower bounds for problems parameterized by clique-width
clique-widthrank-widthfeedback vertex setconnectivity problemmim-width\(d\)-neighbor equivalence\({\sigma\rho}\)-domination
Cites Work
- Title not available (Why is that?)
- Upper bounds to the clique width of graphs
- Approximating clique-width and branch-width
- Title not available (Why is that?)
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- Graph classes with structured neighborhoods and algorithmic applications
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Boolean-width of graphs
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- Graph-Theoretic Concepts in Computer Science
- Faster algorithms for vertex partitioning problems parameterized by clique-width
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
- An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width
- On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
- Output-polynomial enumeration on graphs of bounded (local) linear MIM-width
- The point-set embeddability problem for plane graphs
- A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
Cited In (7)
- Solving problems on generalized convex graphs via mim-width
- Subset feedback vertex set on graphs of bounded independent set size
- Steiner trees for hereditary graph classes: a treewidth perspective
- On the complexity of finding large odd induced subgraphs and odd colorings
- Bounding the mim‐width of hereditary graph classes
- Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
- An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width
This page was built for publication: More applications of the \(d\)-neighbor equivalence: connectivity and acyclicity constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5075752)
