Making Arbitrary Graphs Transitively Orientable: Minimal Comparability Completions

DOI10.1007/11940128_43MaRDI QIDQ5459137zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, F. Mancini, Charis Papadopoulos

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

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Minimal comparability completions of arbitrary graphs
• On transitive orientations with restricted covering graphs
• scientific article; zbMATH DE number 1554932
• scientific article; zbMATH DE number 1003286
• A translation of Gallai's paper: `Transitiv orientierbare Graphen'

Cited in

(15)

• Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
• Dynamically maintaining split graphs
• Sources and sinks in comparability graphs
• A note on transitive orientations with maximum sets of sources and sinks
• Construction of a transitive orientation using B-stable subgraphs
• Minimal comparability completions of arbitrary graphs
• A translation of Gallai's paper: `Transitiv orientierbare Graphen'
• Extending partial suborders
• Characterizing and Computing Minimal Cograph Completions
• scientific article; zbMATH DE number 3939387 (Why is no real title available?)
• Transitive Orientations of Graphs
• On making directed graphs transitive
• scientific article; zbMATH DE number 1554932 (Why is no real title available?)
• To reorient is easier than to orient: An on-line algorithm for reorientation of graphs
• Minimal proper interval completions

This page was built for publication: Making Arbitrary Graphs Transitively Orientable: Minimal Comparability Completions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5459137)