The recognition of indifference digraphs and generalized semiorders

DOI10.1002/(SICI)1097-0118(199602)21:2%3C235::AID-JGT14%3E3.0.CO;2-IzbMATH Open0839.05046OpenAlexW2026445978MaRDI QIDQ4865532FDOQ4865532

Authors: George Steiner 

Publication date: 25 February 1996

Full work available at URL: https://doi.org/10.1002/(sici)1097-0118(199602)21:2%3C235::aid-jgt14%3E3.0.co;2-i

zbMATH Keywords

semiorderslinear time recognition algorithmindifference digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics of partially ordered sets (06A07)

Cited In (8)

• Graphs and digraphs represented by intervals and circular arcs
• Bigraphs/digraphs of Ferrers dimension 2 and asteroidal triple of edges
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Short proofs for interval digraphs
• The recognition of the class of indecomposable digraphs under low hemimorphy
• Forbidden substructure for interval digraphs/bigraphs
• Permutation bigraphs and interval containments
• Circularly compatible ones, \(D\)-circularity, and proper circular-arc bigraphs

This page was built for publication: The recognition of indifference digraphs and generalized semiorders

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