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

(13)

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

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)