Random generation and enumeration of bipartite permutation graphs

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

zbMATH Keywords

enumeration; counting; Dyck path; random generation; bipartite permutation graph; Motzkin path

Mathematics Subject Classification ID

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