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 O ( 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 so that it enumerates those with constraints on the maximum (bi)clique size and/or the number of edges.

Herein, we discuss the existence of overlapping edge unfoldings for convex regular-faced polyhedra. Horiyama and Shoji showed that there are no overlapping edge unfoldings for all platonic solids and five of the Archimedean solids. The remaining five Archimedean solids were found to have edge unfoldings that overlap. In this study, we propose a method called rotational unfolding to find an overlapping edge unfolding of a polyhedron. We show that all the edge unfoldings of an icosidodecahedron, a rhombitruncated cuboctahedron, an n-gonal Archimedean prism (3≤n≤23), an m-gonal Archimedean antiprism (3≤m≤11), and 48 types of Johnson solids do not overlap. Our algorithm finds overlapping edge unfoldings for the snub cube, and 44 types of Johnson solids. We present analytic proof that an overlapping edge unfolding exists in an n-gonal Archimedean prism (n≥24), and an m-gonal Archimedean antiprism (m≥12). Our results prove the existence of overlapping edge unfoldings for convex regular-faced polyhedra.

Given a vertex-weighted undirected graph, to find the vertex cover of minimum weight is called minimum weight vertex cover problem (MWVCP). It is known as an NP-hard problem. In this paper, a fast heuristic for MWVCP is proposed. Our algorithm is based on a simple algorithm called “list-heuristic.” Experimenal results show that our algorithm calculates better solutions in shorter time than approximation algorithms for MWVCP.