Approximating the minimum clique cover and other hard problems in subtree filament graphs |
| |
Authors: | J Mark Keil |
| |
Institution: | a Department of Computer Science, University of Saskatchewan, Saskatoon, Saskatchewan, Canada S7N 5C9 b Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada T6G 2E8 |
| |
Abstract: | Subtree filament graphs are the intersection graphs of subtree filaments in a tree. This class of graphs contains subtree overlap graphs, interval filament graphs, chordal graphs, circle graphs, circular-arc graphs, cocomparability graphs, and polygon-circle graphs. In this paper we show that, for circle graphs, the clique cover problem is NP-complete and the h-clique cover problem for fixed h is solvable in polynomial time. We then present a general scheme for developing approximation algorithms for subtree filament graphs, and give approximation algorithms developed from the scheme for the following problems which are NP-complete on circle graphs and therefore on subtree filament graphs: clique cover, vertex colouring, maximum k-colourable subgraph, and maximum h-coverable subgraph. |
| |
Keywords: | Subtree filament graph Circle graph Clique cover NP-complete Approximation algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|