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

DOI10.1007/978-3-642-13562-0_17MaRDI QIDQ3569074zbMATHOpenAlexFDO

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)