Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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