Efficient non-isomorphic graph enumeration algorithms for several intersection graph classes

DOI10.1016/J.TCS.2024.114591MaRDI QIDQ6549667zbMATH OpenFDO

Authors Jun Kawahara, Toshiki Saitoh, Hirokazu Takeda, Ryo Yoshinaka, Yui Yoshioka

Publication date 4 June 2024

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

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114591

zbMATH Keywords

binary decision diagramsenumerationgraph classesgraph isomorphismstring representation

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
• Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
• Efficient enumeration of non-isomorphic interval graphs
• Efficient enumeration of non-isomorphic Ptolemaic graphs
• A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number

Cites work

• \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
• A partial k-arboretum of graphs with bounded treewidth
• Algorithmic graph theory and perfect graphs
• Complexity of maximum cut on interval graphs
• Computing the Tutte polynomial of a graph of moderate size
• Counting Interval Graphs
• Counting the number of matchings in chordal and chordal bipartite graph classes
• Efficient enumeration of non-isomorphic distance-hereditary graphs and Ptolemaic graphs
• Efficient graph representations
• Enumeration of difference graphs
• Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
• Graph Classes: A Survey
• Introduction to algorithms.
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• OBDD-based representation of interval graphs
• On the OBDD representation of some graph classes
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Random generation and enumeration of bipartite permutation graphs
• Reconfiguring Independent Sets on Interval Graphs
• Representation of graphs by OBDDs
• Reverse search for enumeration
• Subgraph isomorphism in graph classes
• Succinct data structures for families of interval graphs
• Threshold graphs and related topics

This page was built for publication: Efficient non-isomorphic graph enumeration algorithms for several intersection graph classes

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