Permutation bigraphs and interval containments

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

zbMATH Keywords

chain graphpermutation graphindifference bigraphinterval bigraphinterval containment poset

Mathematics Subject Classification ID

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