|
|||||
|
|
Perfect Circular Arc Coloring |
|
| Authors: | Xujin?Chen Zhiquan?Hu |
| Institution: | (1) Institute of Applied Mathematics, Academia Sinica, Beijing, 100080, China;(2) Department of Mathematics, Central China Normal University, Wuhan, 430079, China;(3) Department of Mathematics, University of Hong Kong, Hong Kong, China |
| Abstract: | The circular arc coloring problem is to find a minimum coloring of a set of arcs of a circle so that no two overlapping arcs share a color. This NP-hard problem arises in a rich variety of applications and has been studied extensively. In this paper we present an O(n2 m) combinatorial algorithm for optimally coloring any set of arcs that corresponds to a perfect graph, and propose a new approach to the general circular arc coloring problem.Partially supported by Project 02139 of Education Ministry of China.Supported in part by the Research Grants Council of Hong Kong (Project No. HKU7054/03P) and a seed funding for basic research of HKU. |
| Keywords: | graph coloring circular-arc graph perfect graph matching complexity |
| 本文献已被 SpringerLink 等数据库收录！ | |