The recognition of indifference digraphs and generalized semiorders

DOI10.1002/(SICI)1097-0118(199602)21:2%3C235::AID-JGT14%3E3.0.CO;2-IMaRDI QIDQ4865532zbMATH OpenOpenAlexFDO

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

indifference digraphslinear time recognition algorithmsemiorders

Mathematics Subject Classification ID

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

Cited in

(8)

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