Random generation and enumeration of bipartite permutation graphs

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

zbMATH Keywords

enumerationcountingDyck pathrandom generationbipartite permutation graphMotzkin path

Mathematics Subject Classification ID

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