Permutation bigraphs and interval containments
From MaRDI portal
Publication:401140
DOI10.1016/j.dam.2014.05.020zbMath1298.05165OpenAlexW2044877267MaRDI QIDQ401140
Douglas B. West, Pranab K. Saha, Asim Basu, Malay Kr. 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
Permutations, words, matrices (05A05) Combinatorics of partially ordered sets (06A07) Enumeration in graph theory (05C30) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (4)
Ferrers dimension of grid intersection graphs ⋮ Forbidden substructure for interval digraphs/bigraphs ⋮ Bipartite Analogues of Comparability and Cocomparability Graphs ⋮ Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bandwidth of chain graphs
- Random generation and enumeration of bipartite permutation graphs
- Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs
- Treewidth and minimum fill-in on permutation graphs in linear time
- Labeling bipartite permutation graphs with a condition at distance two
- Bandwidth of bipartite permutation graphs in polynomial time
- Circular-arc graphs with clique cover number two
- Bipartite permutation graphs
- On the Ferrers dimension of a digraph
- Modular decomposition and transitive orientation
- Short proofs for interval digraphs
- Efficient graph representations
- An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
- Representing digraphs using intervals or circular arcs
- An \(O(n)\)-time algorithm for the paired domination problem on permutation graphs
- Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
- Interval digraphs: An analogue of interval graphs
- Containment Graphs, Posets, and Related Classes of Graphs
- Graph Classes: A Survey
- Indifference Digraphs: A Generalization of Indifference Graphs and Semiorders
- Interval bigraphs and circular arc graphs
- The recognition of indifference digraphs and generalized semiorders
- Permutation Graphs and Transitive Graphs
- Partially Ordered Sets
- Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
This page was built for publication: Permutation bigraphs and interval containments
