Random Generation and Enumeration of Proper Interval Graphs

DOI10.1007/978-3-642-00202-1_16MaRDI QIDQ3605496zbMATH OpenOpenAlexFDO

Authors Toshiki Saitoh, Katsuhisa Yamanaka, Masashi Kiyomi, Ryuhei Uehara

Publication date 24 February 2009

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-00202-1_16

zbMATH Keywords

countingenumerationproper interval graphsrandom generationunit interval graphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Random Generation and Enumeration of Bipartite Permutation Graphs
• Random generation and enumeration of bipartite permutation graphs
• On the enumeration of interval graphs
• Efficient enumeration of non-isomorphic interval graphs
• The random selection of unlabeled graphs

Cites work

• A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• A linear time recognition algorithm for proper interval graphs
• A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
• A short proof that `proper = unit'
• A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
• Algorithmic graph theory and perfect graphs
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
• Combinatorial Pattern Matching
• Efficient generation of plane trees.
• Finding Hamiltonian circuits in proper interval graphs
• Graph Classes: A Survey
• Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• scientific article; zbMATH DE number 1754610 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Reverse search for enumeration
• Succinct representation of balanced parentheses and static trees
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• The bandwidth problem for graphs and matrices—a survey
• The NP-completeness of the bandwidth minimization problem
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs

Cited in

(8)

• On the enumeration of interval graphs
• Random Generation and Enumeration of Bipartite Permutation Graphs
• Random generation and enumeration of bipartite permutation graphs
• Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
• Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
• Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs
• Binary bubble languages and cool-lex order
• On characterization and recognition of proper tagged probe interval graphs

This page was built for publication: Random Generation and Enumeration of Proper Interval Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3605496)