Algorithms for Weakly Triangulated Graphs

Arvind Raghunathan

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-89-503

, 1989

http://www2.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},
    Year= {1989},
    Month= {Apr},
    Url= {http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/1989/5196.html
%F Raghunathan:CSD-89-503