Search

A graph is chordal if and only if it has no chordless cycle of length more than three. The set of maximal cliques in a chordal graph admits special tree structures called clique trees. A perfect sequence is a sequence of maximal cliques obtained by using the reverse order of repeatedly removing the leaves of a clique tree. This paper addresses the problem of enumerating all the perfect sequences. Although this problem has statistical applications, no efficient algorithm has been proposed. There are two difficulties with developing this type of algorithms. First, a chordal graph does not generally have a unique clique tree. Second, a perfect sequence can normally be generated by two or more distinct clique trees. Thus it is hard using a straightforward way to generate perfect sequences from each possible clique tree. In this paper, we propose a method to enumerate perfect sequences without constructing clique trees. As a result, we have developed the first polynomial delay algorithm for dealing with this problem. In particular, the time complexity of the algorithm on average is O(1) for each perfect sequence. [ABSTRACT FROM AUTHOR]

For a bipartite graph G = (V,E), an edge coloring of G is a coloring of the edges of G such that any two adjacent edges are colored in different colors. In this paper, we consider the problem of enumerating all edge colorings with the fewest number of colors. We propose a simple polynomial delay algorithm whose amortized time complexity is O(V) per output, whereas the previous fastest algorithm took O(E log V) time per output. Although the delay of the algorithm is O(EV), the delay of our algorithm can be reduced to O(V) by using a simple modification with a queue of polynomial size. We show an improvement to reduce the space complexity from O(VE) to O(E + V). Furthermore, we obtain a lower bound $$ (E - \hat V + 1)\max \{ 2^{\Delta - 3} ,2(\hat V/2 + 1)^{\Delta - 3} /(\Delta - 1)\} /\Delta $$ of the number of edge colorings included in G, where Δ is the maximum degree and $$ \hat V $$ is the set of vertices of the maximum degree. [ABSTRACT FROM AUTHOR]