An O(n^2)-time algorithm for the minimal interval completion problem

DOI10.1007/978-3-642-13562-0_17zbMATH Open1284.05278OpenAlexW2498850858MaRDI QIDQ3569074FDOQ3569074

Authors: Christophe Crespelle, Ioan Todinca 

Publication date: 17 June 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13562-0_17

Recommendations

• An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem
• Algorithms – ESA 2005
• Minimal Interval Completion Through Graph Exploration
• Minimal interval completion through graph exploration
• Minimal Proper Interval Completions

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Cited In (9)

• Minimal Interval Completion Through Graph Exploration
• An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem
• Algorithms – ESA 2005
• Approximating the path-distance-width for AT-free graphs and graphs in related classes
• Characterizing Minimal Interval Completions
• Minimal Proper Interval Completions
• An integer programming model for the minimum interval graph completion problem
• A Subexponential Parameterized Algorithm for Proper Interval Completion
• Linear-Time Recognition of Probe Interval Graphs

This page was built for publication: An \({\mathcal{O}}(n^2)\)-time algorithm for the minimal interval completion problem

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