Strict chordal and strict split digraphs

DOI10.1016/J.DAM.2016.02.009MaRDI QIDQ516787zbMATH OpenOpenAlexWikidataFDO

Authors Pavol Hell, César Hernández-Cruz

Publication date 15 March 2017

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2016.02.009

zbMATH Keywords

chordal digraphperfect digraphrecognition algorithmsplit digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85)

Cites work

• A Characterization of Comparability Graphs and of Interval Graphs
• Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Chordal digraphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4168705 (Why is no real title available?)
• scientific article; zbMATH DE number 3910422 (Why is no real title available?)
• scientific article; zbMATH DE number 15355 (Why is no real title available?)
• scientific article; zbMATH DE number 165071 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 2079335 (Why is no real title available?)
• scientific article; zbMATH DE number 3448611 (Why is no real title available?)
• Incidence matrices and interval graphs
• Interval digraphs: An analogue of interval graphs
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• Partitioning chordal graphs into independent sets and cliques
• Perfect digraphs
• Recognizing Berge graphs
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Representation of a finite graph by a set of intervals on the real line
• Split digraphs
• Subpath acyclic digraphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The ellipsoid method and its consequences in combinatorial optimization
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The LBFS structure and recognition of interval graphs
• The strong perfect graph theorem
• Toward Characterization of Perfect Elimination Digraphs

Cited in

(6)

• Strict chordal digraphs viewed as graphs with distinguished edges
• Splitting digraphs
• Unit and proper bitolerance digraphs
• Semi-strict chordal digraphs
• Semi-strict chordality of digraphs
• Strong arc decompositions of split digraphs

This page was built for publication: Strict chordal and strict split digraphs

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