Recognizing interval digraphs and interval bigraphs in polynomial time
From MaRDI portal
Publication:1377666
DOI10.1016/S0166-218X(97)00027-9zbMATH Open0890.68103OpenAlexW2068456050MaRDI QIDQ1377666FDOQ1377666
Authors: Haiko Müller 
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
Recommendations
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Interval digraphs: An analogue of interval graphs
- Title not available (Why is that?)
- On rigid circuit graphs
- 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
- Characterizations of strongly chordal graphs
- Bipartite permutation graphs
- Node-Deletion Problems on Bipartite Graphs
- Weakly triangulated graphs
- Comparability graphs and a new matroid
- Perfect Elimination and Chordal Bipartite Graphs
- Treewidth and Pathwidth of Permutation Graphs
- Title not available (Why is that?)
- Maximum matching in a convex bipartite graph
- Title not available (Why is that?)
- Classes of bipartite graphs related to chordal graphs
- Indifference Digraphs: A Generalization of Indifference Graphs and Semiorders
- The recognition of indifference digraphs and generalized semiorders
- Sur deux propriétés des classes d'ensembles
- Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph
- Title not available (Why is that?)
- Connection digraphs and second-order line digraphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Characterizing intersection classes of graphs
Cited In (46)
- Asteroidal Triple of Edges in Bichordal Graphs: A Complete list
- Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
- On Restrictions of Balanced 2-Interval Graphs
- Simple Geometrical Intersection Graphs
- Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
- Algorithms for interval catch digraphs
- List matrix partitions of graphs representing geometric configurations
- Boxicity of circular arc graphs
- Boolean rank of upset tournament matrices
- 2-tree probe interval graphs have a large obstruction set
- Bigraphs/digraphs of Ferrers dimension 2 and asteroidal triple of edges
- Intersection representation of digraphs in trees with few leaves
- Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
- An interval digraph in relation to its associated bipartite graph
- On orthogonal ray graphs
- Subclasses of circular-arc bigraphs: Helly, normal and proper
- Minimum cost homomorphisms with constrained costs
- Tractabilities and intractabilities on geometric intersection graphs
- On computing longest paths in small graph classes
- Linear-time modular decomposition of directed graphs
- Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
- Recognizing interval bigraphs by forbidden patterns
- Adjacency matrices of probe interval graphs
- A min-max property of chordal bipartite graphs with applications
- On the kernel and related problems in interval digraphs
- Bipartite Analogues of Comparability and Cocomparability Graphs
- Uniquely restricted matchings in interval graphs
- Recognition and characterization of chronological interval digraphs
- Interval bigraphs and circular arc graphs
- A recognition algorithm for adjusted interval digraphs
- Interval bigraphs are unit grid intersection graphs
- New characterizations of proper interval bigraphs
- Forbidden substructure for interval digraphs/bigraphs
- Adjusted interval digraphs
- Classes of intersection digraphs with good algorithmic properties
- Permutation bigraphs and interval containments
- On orthogonal ray trees
- A characterization of 2-tree proper interval 3-graphs
- Characterizations for unit interval bigraphs
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- Miscellaneous digraph classes
- Chordal multipartite graphs and chordal colorings
- Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
- Strict chordal and strict split digraphs
- Biclique graphs of interval bigraphs
- Normal Helly circular-arc graphs and its subclasses
This page was built for publication: Recognizing interval digraphs and interval bigraphs in polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377666)
