Random generation and enumeration of bipartite permutation graphs
From MaRDI portal
Publication:414425
DOI10.1016/j.jda.2011.11.001zbMath1241.05050OpenAlexW2060809502MaRDI 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
Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (9)
Permutation bigraphs and interval containments ⋮ Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs ⋮ Succinct permutation graphs ⋮ Efficient enumeration of non-isomorphic distance-hereditary graphs and related graphs ⋮ Subgraph isomorphism in graph classes ⋮ Efficient enumeration of non-isomorphic distance-hereditary graphs and Ptolemaic graphs ⋮ The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation ⋮ Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs ⋮ A polynomial-time algorithm for finding critical nodes in bipartite 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
This page was built for publication: Random generation and enumeration of bipartite permutation graphs