On minimal augmentation of a graph to obtain an interval graph
From MaRDI portal
Publication:1154281
DOI10.1016/0022-0000(81)90022-2zbMath0464.68065OpenAlexW2035632654MaRDI QIDQ1154281
Toshinobu Kashiwabara, Toshio Fujisawa, Tatsuo Ohtsuki, Hajimu Mori
Publication date: 1981
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(81)90022-2
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (9)
On the effectiveness of the incremental approach to minimal chordal edge modification ⋮ Linear-time minimal cograph editing ⋮ An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ An \(O(n^2)\) time algorithm for the minimal permutation completion problem ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ Minimal interval completion through graph exploration ⋮ An $$\mathcal {O}(n^2)$$ Time Algorithm for the Minimal Permutation Completion Problem ⋮ Interval graphs and related topics
Cites Work
- Unnamed Item
- Unnamed Item
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
- Incidence matrices and interval graphs
- Triangulated graphs and the elimination process
- One-dimensional logic gate assignment and interval graphs
- Representation of a finite graph by a set of intervals on the real line
- A Fast Algorithm for Finding an Optimal Ordering for Vertex Elimination on a Graph
- Algorithmic Aspects of Vertex Elimination on Graphs
- `` Strong NP-Completeness Results
- A Characterization of Comparability Graphs and of Interval Graphs
This page was built for publication: On minimal augmentation of a graph to obtain an interval graph
