AN OPTIMAL GREEDY HEURISTIC TO COLOR INTERVAL-GRAPHS

被引：98

作者：

OLARIU, S

机构：

[1] Department of Computer Science, Old Dominion University, Norfolk

来源：

INFORMATION PROCESSING LETTERS | 1991年 / 37卷 / 01期

关键词：

COLORING; HEURISTICS; INTERVAL GRAPHS; LINEAR-TIME ALGORITHMS;

D O I：

10.1016/0020-0190(91)90245-D

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We characterize interval graphs in terms of a certain linear order on their vertex set. It turns out that with this linear order, the well-known greedy heuristic "always use the smallest available color" yields an exact coloring algorithm for interval graphs. In addition, the heuristic can be implemented to run in linear time.

引用

页码：21 / 25

页数：5

共 14 条

[1] TESTING FOR CONSECUTIVE ONES PROPERTY, INTERVAL GRAPHS, AND GRAPH PLANARITY USING PQ-TREE ALGORITHMS [J].