Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs

DOI10.1016/J.TCS.2019.04.017MaRDI QIDQ5919325zbMATH OpenOpenAlexFDO

Authors Kazuaki Yamazaki, Toshiki Saitoh, Masashi Kiyomi, Ryuhei Uehara

Publication date 16 January 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2019.04.017

zbMATH Keywords

enumerationgraph isomorphisminterval graphnonisomorphic graphspermutation graphreverse search

Mathematics Subject Classification ID

Enumeration in graph theory (05C30)

Recommendations

• Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
• Efficient enumeration of non-isomorphic interval graphs
• On the enumeration and counting of minimal dominating sets in interval and permutation graphs
• Random Generation and Enumeration of Proper Interval Graphs
• Polynomial-delay enumeration of monotonic graph classes

Cites work

• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Algorithmic graph theory and perfect graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Counting Interval Graphs
• Efficient graph representations
• Fully dynamic algorithm for recognition and modular decomposition of permutation 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 477971 (Why is no real title available?)
• Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
• Listing Chordal Graphs and Interval Graphs
• Modular decomposition and transitive orientation
• On testing isomorphism of permutation graphs
• Random generation and enumeration of bipartite permutation graphs
• Reverse search for enumeration
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Transitiv orientierbare Graphen

Cited in

(18)

• The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation
• Distributed interactive proofs for the recognition of some geometric intersection graph classes
• Efficient enumeration of non-isomorphic distance-hereditary graphs and Ptolemaic graphs
• On enumeration of some non-isomorphic edge complete semigraphs
• Enumeration of irredundant forests
• Polynomial-delay enumeration of monotonic graph classes
• Enumerating rooted graphs with reflectional block structures
• scientific article; zbMATH DE number 4063148 (Why is no real title available?)
• Efficient enumeration of non-isomorphic interval graphs
• Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
• Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs
• Efficient non-isomorphic graph enumeration algorithms for several intersection graph classes
• Compact distributed certification of geometric graph classes
• Constant time enumeration of weighted trees
• Generalizing Roberts' characterization of unit interval graphs
• Enumeration of interval graphs and d-representable complexes
• The bend number of cocomparability graphs
• Efficient enumeration of non-isomorphic Ptolemaic graphs

This page was built for publication: Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs

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