Proper Interval Vertex Deletion

DOI10.1007/978-3-642-17493-3_22zbMath1309.68157OpenAlexW2114502544MaRDI QIDQ3058706

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

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

Related Items (6)

Polynomial kernels for proper interval completion and related problems ⋮ Contracting graphs to paths and trees ⋮ Unit interval editing is fixed-parameter tractable ⋮ Measuring Indifference: Unit Interval Vertex Deletion ⋮ Polynomial Kernels for Proper Interval Completion and Related Problems ⋮ An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs

Cites Work

• Unnamed Item
• Feedback vertex set on AT-free graphs
• Chordal deletion is fixed-parameter tractable
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• On linear and circular structure of (claw, net)-free graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Structure theorems for some circular-arc graphs
• Measuring Indifference: Unit Interval Vertex Deletion
• Representation of a finite graph by a set of intervals on the real line
• Wheel-Free Deletion Is W[2-Hard]
• On Feedback Vertex Set New Measure and New Structures
• Interval Completion Is Fixed Parameter Tractable
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph Classes: A Survey
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Improved Parameterized Upper Bounds for Vertex Cover

This page was built for publication: Proper Interval Vertex Deletion