Proper Interval Vertex Deletion

DOI10.1007/978-3-642-17493-3_22MaRDI QIDQ3058706zbMATH OpenOpenAlexFDO

Authors Yngve Villanger

Publication date 7 December 2010

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-17493-3_22

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Proper interval vertex deletion
• Unit interval vertex deletion: fewer vertices are relevant
• A Polynomial Kernel for Proper Interval Vertex Deletion
• Vertex deletion parameterized by elimination distance and even less
• Polynomial Kernel for Interval Vertex Deletion
• Vertex deletion for 3D Delaunay triangulations
• A polynomial kernel for \textsc{Proper Interval Vertex Deletion}
• Interval vertex deletion admits a polynomial kernel
• Deleting vertices and interlacing Laplacian eigenvalues
• Vertex deletion problems on chordal graphs

Cites work

• Algorithmic Aspects of Vertex Elimination on Graphs
• Chordal deletion is fixed-parameter tractable
• Feedback vertex set on AT-free graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Graph Classes: A Survey
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• Improved Parameterized Upper Bounds for Vertex Cover
• Interval Completion Is Fixed Parameter Tractable
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Measuring indifference: unit interval vertex deletion
• On feedback vertex set new measure and new structures
• On linear and circular structure of (claw, net)-free graphs
• Representation of a finite graph by a set of intervals on the real line
• Structure theorems for some circular-arc graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The node-deletion problem for hereditary properties is NP-complete
• Wheel-Free Deletion Is W[2]-Hard

Cited in

(6)

• Proper interval vertex deletion
• An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs
• A polynomial kernel for \textsc{Proper Interval Vertex Deletion}
• Measuring indifference: unit interval vertex deletion
• Polynomial kernels for proper interval completion and related problems
• Polynomial kernels for proper interval completion and related problems

This page was built for publication: Proper Interval Vertex Deletion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3058706)