Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs

DOI10.1007/978-3-031-27051-2_14MaRDI QIDQ6091158zbMATH OpenFDO

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

Publication date 24 November 2023

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

Full work available at URL https://arxiv.org/abs/2212.07119

zbMATH Keywords

binary decision diagramsenumerationgraph classesgraph isomorphismstring representation

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: Intersection graphs are well-studied in the area of graph algorithms. Some intersection graph classes are known to have algorithms enumerating all unlabeled graphs by reverse search. Since these algorithms output graphs one by one and the numbers of graphs in these classes are vast, they work only for a small number of vertices. Binary decision diagrams (BDDs) are compact data structures for various types of data and useful for solving optimization and enumeration problems. This study proposes enumeration algorithms for five intersection graph classes, which admit $mathrmO(n)$-bit string representations for their member graphs. Our algorithm for each class enumerates all unlabeled graphs with $n$ vertices over BDDs representing the binary strings in time polynomial in $n$. Moreover, our algorithms are extended to enumerate those with constraints on the maximum (bi)clique size and/or the number of edges.

Cites work

• Algorithmic graph theory and perfect graphs
• Computing the Tutte polynomial of a graph of moderate size
• 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
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Random generation and enumeration of bipartite permutation graphs
• Random Generation and Enumeration of Proper Interval Graphs
• Reverse search for enumeration
• Subgraph isomorphism in graph classes
• Threshold graphs and related topics

Cited in

(5)

• Efficient enumeration of non-isomorphic interval graphs
• scientific article; zbMATH DE number 6180530 (Why is no real title available?)
• Polynomial-Time Algorithms for Subgraph Isomorphism in Small Graph Classes of Perfect Graphs
• The bend number of cocomparability graphs
• Efficient enumeration of non-isomorphic Ptolemaic graphs

This page was built for publication: Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs

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