Recognizing interval digraphs and interval bigraphs in polynomial time
From MaRDI portal
Publication:1377666
DOI10.1016/S0166-218X(97)00027-9zbMath0890.68103OpenAlexW2068456050MaRDI QIDQ1377666
Publication date: 23 June 1998
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: http://www.elsevier.com/locate/dam
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items (39)
Subclasses of circular-arc bigraphs: Helly, normal and proper ⋮ Chordal multipartite graphs and chordal colorings ⋮ On orthogonal ray graphs ⋮ Adjacency matrices of probe interval graphs ⋮ Biclique graphs of interval bigraphs ⋮ Recognition and characterization of chronological interval digraphs ⋮ Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs ⋮ Recognizing interval bigraphs by forbidden patterns ⋮ New characterizations of proper interval bigraphs ⋮ On the kernel and related problems in interval digraphs ⋮ Forbidden substructure for interval digraphs/bigraphs ⋮ Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms ⋮ Boolean rank of upset tournament matrices ⋮ Classes of intersection digraphs with good algorithmic properties ⋮ On orthogonal ray trees ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ Bipartite Analogues of Comparability and Cocomparability Graphs ⋮ A min-max property of chordal bipartite graphs with applications ⋮ Intersection representation of digraphs in trees with few leaves ⋮ Boxicity of circular arc graphs ⋮ Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ List matrix partitions of graphs representing geometric configurations ⋮ Strict chordal and strict split digraphs ⋮ A characterization of 2-tree proper interval 3-graphs ⋮ Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs ⋮ Linear-time modular decomposition of directed graphs ⋮ Bigraphs/digraphs of Ferrers dimension 2 and asteroidal triple of edges ⋮ Recognition and drawing of stick graphs ⋮ ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES ⋮ Simple Geometrical Intersection Graphs ⋮ Minimum Cost Homomorphisms with Constrained Costs ⋮ Interval bigraphs are unit grid intersection graphs ⋮ Adjusted Interval Digraphs ⋮ 2-tree probe interval graphs have a large obstruction set ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ Miscellaneous Digraph Classes ⋮ Uniquely Restricted Matchings in Interval Graphs ⋮ Asteroidal Triple of Edges in Bichordal Graphs: A Complete list
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph
- On rigid circuit graphs
- Weakly triangulated graphs
- Characterizations of strongly chordal graphs
- Characterizing intersection classes of graphs
- Bipartite permutation graphs
- Connection digraphs and second-order line digraphs
- Classes of bipartite graphs related to chordal graphs
- Comparability graphs and a new matroid
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Representation of a finite graph by a set of intervals on the real line
- Interval digraphs: An analogue of interval graphs
- Node-Deletion Problems on Bipartite Graphs
- Perfect Elimination and Chordal Bipartite Graphs
- Indifference Digraphs: A Generalization of Indifference Graphs and Semiorders
- Treewidth and Pathwidth of Permutation Graphs
- The recognition of indifference digraphs and generalized semiorders
- Maximum matching in a convex bipartite graph
- Sur deux propriétés des classes d'ensembles
This page was built for publication: Recognizing interval digraphs and interval bigraphs in polynomial time
