Proper Interval Vertex Deletion

DOI10.1007/978-3-642-17493-3_22zbMATH Open1309.68157OpenAlexW2114502544MaRDI QIDQ3058706FDOQ3058706

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)

Cites Work

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

Cited In (6)

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

Recommendations

• Vertex Deletion for 3D Delaunay Triangulations 👍 👎
• A Polynomial Kernel for Proper Interval Vertex Deletion 👍 👎
• Unit interval vertex deletion: fewer vertices are relevant 👍 👎
• Proper interval vertex deletion 👍 👎
• A Polynomial Kernel for Proper Interval Vertex Deletion 👍 👎
• Vertex deletion problems on chordal graphs 👍 👎
• Vertex deletion parameterized by elimination distance and even less 👍 👎
• Interval Vertex Deletion Admits a Polynomial Kernel 👍 👎
• Polynomial Kernel for Interval Vertex Deletion 👍 👎
• Deleting vertices and interlacing Laplacian eigenvalues 👍 👎

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)