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},
    Abstract = {A graph <i>G</i> = (<i>V</i>,<i>E</i>) is said to be weakly triangulated if neither <i>G</i> nor <i>G^c</i>, the complement of <i>G</i>, 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 <i>O</i> (<i>e</i>^.<i>v^3</i>) algorithms to find a maximum clique and a minimum coloring of a weakly triangulated graph. Performing these algorithms on the complement graph gives <i>O</i> (<i>v^5</i>) algorithms to find a maximum independent set and a minimum clique cover of such a graph.   <p>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 <i>O</i> (<i>e</i>^.<i>v^2</i>) algorithms to find a maximum clique and a minimum coloring of a weakly triangulated graph. We thus obtain an <i>O</i> (<i>v^4</i>) algorithm to find a maximum independent set and a minimum clique cover of such a graph. We also provide <i>O</i> (<i>v^5</i>) algorithms for weighted versions of these problems.}
}

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