Algorithms for Weakly Triangulated Graphs
Arvind Raghunathan
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-89-503
April 1989
http://www.eecs.berkeley.edu/Pubs/TechRpts/1989/CSD-89-503.pdf
A graph G = (V,E) is said to be weakly triangulated if neither G nor G^c, the complement of G, contain chordless or induced cycles of length greater than four. Ryan Hayward showed that weakly triangulated graphs are perfect. Later, Hayward, Hoang and Maffray obtained O (e^.v^3) algorithms to find a maximum clique and a minimum coloring of a weakly triangulated graph. Performing these algorithms on the complement graph gives O (v^5) algorithms to find a maximum independent set and a minimum clique cover of such a graph.
It was shown in [13-16] that weakly triangulated graphs play a crucial role in polygon decomposition problems. Several polygon decomposition problems can be formulated as the problem of covering a weakly triangulated graph with a minimum number of cliques. Motivated by this, we now improve on the algorithms of Hayward, Hoang and Maffray by providing O (e^.v^2) algorithms to find a maximum clique and a minimum coloring of a weakly triangulated graph. We thus obtain an O (v^4) algorithm to find a maximum independent set and a minimum clique cover of such a graph. We also provide O (v^5) algorithms for weighted versions of these problems.
BibTeX citation:
@techreport{Raghunathan:CSD-89-503,
Author = {Raghunathan, Arvind},
Title = {Algorithms for Weakly Triangulated Graphs},
Institution = {EECS Department, University of California, Berkeley},
Year = {1989},
Month = {Apr},
URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1989/5196.html},
Number = {UCB/CSD-89-503}
}
EndNote citation:
%0 Report %A Raghunathan, Arvind %T Algorithms for Weakly Triangulated Graphs %I EECS Department, University of California, Berkeley %D 1989 %@ UCB/CSD-89-503 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1989/5196.html %F Raghunathan:CSD-89-503