Approximation and kernelization for chordal vertex deletion
From MaRDI portal
(Redirected from Approximation and kernelization for chordal vertex deletion)
Approximation and kernelization for chordal vertex deletion (scientific article; zbMATH DE number 6935607)
Approximation and kernelization for chordal vertex deletion (scientific article; zbMATH DE number 6935607)
Recommendations
Cites work
- (Meta) kernelization
- \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- A 4k^2 kernel for feedback vertex set
- A characterisation of rigid circuit graphs
- A cubic kernel for feedback vertex set and loop cutset
- A New Algorithm for Generating All the Maximal Independent Sets
- A polynomial kernel for distance-hereditary vertex deletion
- A Polynomial Kernel for Proper Interval Vertex Deletion
- A Separator Theorem for Chordal Graphs
- A Subexponential Parameterized Algorithm for Proper Interval Completion
- A unified approach to approximating resource allocation and scheduling
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Approximation and tidying -- a problem kernel for s-plex cluster vertex deletion
- Chordal deletion is fixed-parameter tractable
- Chordal Deletion Is Fixed-Parameter Tractable
- Chordal editing is fixed-parameter tractable
- Compression via Matroids
- Erdős-Pósa property of chordless cycles and its applications
- Exploring the subexponential complexity of completion problems
- Feedback vertex set inspired kernel for chordal vertex deletion
- Graph Classes: A Survey
- scientific article; zbMATH DE number 2079369 (Why is no real title available?)
- scientific article; zbMATH DE number 3420184 (Why is no real title available?)
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Interval deletion is fixed-parameter tractable
- Kernelization -- preprocessing with a guarantee
- Kernelization using structural parameters on sparse graph classes
- Linear recognition of almost interval graphs
- Multiway cuts in node weighted graphs
- Nondeterminism within $P^ * $
- On diameters and radii of bridged graphs
- On Independent Circuits Contained in a Graph
- On Linear Time Minor Tests with Depth-First Search
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- Parameterized algorithms
- Parameterized complexity of vertex colouring
- Parameterized complexity of vertex deletion into perfect graph classes
- Parametrized complexity theory.
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Recent developments in kernelization: a survey
- Recognizing tough graphs is NP-hard
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Subexponential parameterized algorithm for interval completion
- The \(k\)-disjoint paths problem on chordal graphs
- The Complexity of Multiterminal Cuts
- The node-deletion problem for hereditary properties is NP-complete
- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
- Unit interval vertex deletion: fewer vertices are relevant
- Vertex packings: Structural properties and algorithms
Cited in
(37)- Vertex deletion problems on chordal graphs
- On the approximate compressibility of connected vertex cover
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
- Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
- Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
- Structural parameterizations with modulator oblivion
- Erdős-Pósa property of chordless cycles and its applications
- Parameterized complexity of vertex deletion into perfect graph classes
- Chordal Deletion Is Fixed-Parameter Tractable
- Kernelization through Tidying
- Parameterized complexity of vertex deletion into perfect graph classes
- Feedback vertex set inspired kernel for chordal vertex deletion
- Approximation and kernelization for chordal vertex deletion
- Feedback vertex set inspired kernel for chordal vertex deletion
- Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
- scientific article; zbMATH DE number 7559376 (Why is no real title available?)
- Deletion in Abstract Voronoi Diagrams in Expected Linear Time.
- Vertex deletion problems on chordal graphs
- A polynomial kernel for block graph deletion
- scientific article; zbMATH DE number 7651188 (Why is no real title available?)
- Chordless Cycle Packing Is Fixed-Parameter Tractable
- Quadratic vertex kernel for split vertex deletion
- A polynomial kernel for distance-hereditary vertex deletion
- A polynomial kernel for 3-leaf power deletion
- scientific article; zbMATH DE number 7765420 (Why is no real title available?)
- On the Parameterized Complexity of Clique Elimination Distance
- Polynomial Kernel for Interval Vertex Deletion
- A survey of parameterized algorithms and the complexity of edge modification
- Search-space reduction via essential vertices
- Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
- A constant-factor approximation for weighted bond cover
- On the parameterized complexity of multiway near-separator
- Tight bounds for chordal/interval vertex deletion parameterized by treewidth
- Hitting meets packing: how hard can it be?
- Parameterized geometric graph modification with disk scaling
- A vertex incremental approach for maintaining chordality
This page was built for publication: Approximation and kernelization for chordal vertex deletion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4586151)
