Cycle-free partial orders and chordal comparability graphs

DOI10.1007/BF00385814zbMath0736.06005MaRDI QIDQ1182042

Tze-Heng Ma, Jeremy P. Spinrad

Publication date: 27 June 1992

Published in: Order (Search for Journal in Brave)

zbMATH Keywords

dimensionlinear time algorithmcycle-free partial orderschordal comparability graphstransitive closure of a digraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)

Related Items (7)

Split orders ⋮ Transitive closure for restricted classes of partial orders ⋮ An implicit representation of chordal comparability graphs in linear time ⋮ On \(k\)-tree containment graphs of paths in a tree ⋮ The dimension of cycle-free orders ⋮ PARTIALLY ORDERED SETS AND COMBINATORY OBJECTS OF THE PYRAMIDAL STRUCTURE ⋮ Construction of a simple elimination scheme for a chordal comparability graph in linear time

Cites Work

• Matrix multiplication via arithmetic progressions
• A characterisation of rigid circuit graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• On Comparability and Permutation Graphs
• Minimizing Setups for Cycle-Free Ordered Sets
• Algorithmic Aspects of Vertex Elimination on Graphs
• Partially Ordered Sets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Cycle-free partial orders and chordal comparability graphs