Random generation and enumeration of bipartite permutation graphs
From MaRDI portal
Publication:414425
DOI10.1016/j.jda.2011.11.001zbMath1241.05050MaRDI QIDQ414425
Ryuhei Uehara, Toshiki Saitoh, Katsuhisa Yamanaka, Yota Otachi
Publication date: 11 May 2012
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2011.11.001
05C30: Enumeration in graph theory
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Related Items
Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs, Permutation bigraphs and interval containments, Subgraph isomorphism in graph classes, The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation, Efficient enumeration of non-isomorphic distance-hereditary graphs and Ptolemaic graphs, A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs, Succinct permutation graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A simple optimal representation for balanced parentheses
- Bipartite permutation graphs
- A short proof that `proper = unit'
- Efficient graph representations
- Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
- A bijection between ordered trees and 2-Motzkin paths and its many consequences
- Efficient generation of plane trees.
- Algorithmic graph theory and perfect graphs
- Connected permutation graphs
- Succinct Representation of Balanced Parentheses and Static Trees
- Random Generation and Enumeration of Bipartite Permutation Graphs
- On testing isomorphism of permutation graphs
- A Linear Time Algorithm for Deciding Interval Graph Isomorphism
- Graph Classes: A Survey
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs