Making Arbitrary Graphs Transitively Orientable: Minimal Comparability Completions
From MaRDI portal
Publication:5459137
DOI10.1007/11940128_43zbMath1135.05305MaRDI QIDQ5459137
Pinar Heggernes, Charis Papadopoulos, Federico Mancini
Publication date: 24 April 2008
Published in: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11940128_43
68Q25: Analysis of algorithms and problem complexity
05C85: Graph algorithms (graph-theoretic aspects)
05C20: Directed graphs (digraphs), tournaments
Related Items
Minimal proper interval completions, Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions, Dynamically maintaining split graphs, Characterizing and Computing Minimal Cograph Completions