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

DOI10.1016/j.tcs.2012.12.031zbMath1295.05227OpenAlexW2084783792MaRDI QIDQ391090

Ioan Todinca, Christophe Crespelle

Publication date: 10 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.12.031

zbMATH Keywords

graph algorithmsinterval graphsminimal interval completions

Mathematics Subject Classification ID

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

Related Items (6)

On the effectiveness of the incremental approach to minimal chordal edge modification ⋮ Linear-time minimal cograph editing ⋮ Fully dynamic representations of interval graphs ⋮ An \(O(n^2)\) time algorithm for the minimal permutation completion problem ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ An $$\mathcal {O}(n^2)$$ Time Algorithm for the Minimal Permutation Completion Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Minimal triangulations of graphs: a survey
• Minimal proper interval completions
• Minimal split completions
• Minimal interval completion through graph exploration
• On minimal augmentation of a graph to obtain an interval graph
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Algorithmic graph theory and perfect graphs
• Minimal comparability completions of arbitrary graphs
• Incidence matrices, interval graphs and seriation in archeology
• An ${\mathcal{O}}(n^2)$ -time Algorithm for the Minimal Interval Completion Problem
• Complexity of Finding Embeddings in a k-Tree
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Computing the Minimum Fill-In is NP-Complete
• Mapping the genome
• Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
• Algorithms – ESA 2005
• A Characterization of Comparability Graphs and of Interval Graphs
• Fully Dynamic Representations of Interval Graphs

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