Permutation bigraphs and interval containments
DOI10.1016/J.DAM.2014.05.020zbMATH Open1298.05165OpenAlexW2044877267MaRDI QIDQ401140FDOQ401140
Authors: P. K. Saha, Asim Basu, Douglas B. West, Malay K. Sen 
Publication date: 26 August 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2014.05.020
Recommendations
- Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
- Characterizations for unit interval bigraphs
- New characterizations of proper interval bigraphs and proper circular arc bigraphs
- scientific article; zbMATH DE number 1743762
- Recognizing interval digraphs and interval bigraphs in polynomial time
Permutations, words, matrices (05A05) Enumeration in graph theory (05C30) Graph representations (geometric and intersection representations, etc.) (05C62) Combinatorics of partially ordered sets (06A07)
Cites Work
- Interval digraphs: An analogue of interval graphs
- Title not available (Why is that?)
- Graph Classes: A Survey
- Modular decomposition and transitive orientation
- Efficient graph representations
- Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
- Bipartite permutation graphs
- Partially Ordered Sets
- Permutation Graphs and Transitive Graphs
- Bandwidth of chain graphs
- Containment Graphs, Posets, and Related Classes of Graphs
- On the Ferrers dimension of a digraph
- Representing digraphs using intervals or circular arcs
- Interval bigraphs and circular arc graphs
- Title not available (Why is that?)
- Treewidth and minimum fill-in on permutation graphs in linear time
- Bandwidth of bipartite permutation graphs in polynomial time
- Circular-arc graphs with clique cover number two
- Labeling bipartite permutation graphs with a condition at distance two
- Short proofs for interval digraphs
- An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
- An \(O(n)\)-time algorithm for the paired domination problem on permutation graphs
- Random generation and enumeration of bipartite permutation graphs
- Indifference Digraphs: A Generalization of Indifference Graphs and Semiorders
- The recognition of indifference digraphs and generalized semiorders
- Title not available (Why is that?)
- Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
- Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs
Cited In (9)
- Title not available (Why is that?)
- Min orderings and list homomorphism dichotomies for graphs and signed graphs
- Title not available (Why is that?)
- Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
- Recognizing interval bigraphs by forbidden patterns
- Bipartite Analogues of Comparability and Cocomparability Graphs
- Forbidden substructure for interval digraphs/bigraphs
- Ferrers dimension of grid intersection graphs
- Canonical antichains of unit interval and bipartite permutation graphs
This page was built for publication: Permutation bigraphs and interval containments
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q401140)
