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

Mathematics Subject Classification ID

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

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

Cited in

(12)

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

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)