On minimal augmentation of a graph to obtain an interval graph

DOI10.1016/0022-0000(81)90022-2zbMath0464.68065MaRDI QIDQ1154281

Tatsuo Ohtsuki, Hajimu Mori, Toshinobu Kashiwabara, Toshio Fujisawa

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

zbMATH Keywords

algorithm; interval graph; realization; consecutive ones property; PQ-tree; clique augmentation

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

Related Items

Minimal interval completion through graph exploration, 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