LINEAR ALGORITHM FOR OPTIMAL PATH COVER PROBLEM ON INTERVAL-GRAPHS

被引：69

作者：

ARIKATI, SR ^{[1
]}

RANGAN, CP ^{[1
]}

机构：

[1] INDIAN INST TECHNOL, DEPT COMP SCI & ENGN, MADRAS 600036, TAMIL NADU, INDIA

来源：

INFORMATION PROCESSING LETTERS | 1990年 / 35卷 / 03期

关键词：

Data structures; design of algorithms; interval graphs; path covering;

D O I：

10.1016/0020-0190(90)90064-5

中图分类号：

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

学科分类号：

0812 ;

摘要：

A path cover of a graph G is a set of vertex-disjoint paths that cover all the vertices of G. An optimal path cover of G is a path cover of minimum cardinality. This problem is known to be NP-complete for arbitrary graphs. We present a linear algorithm for this problem on interval graphs. Given the adjacency lists of an interval graph with n vertices and m edges, our algorithm runs in O(m+n) time. © 1990.

引用

页码：149 / 153

页数：5

共 13 条

[1]

Boesch F. T., 1974, GRAPH COMBINATOR, V406, P201

[2] MINIMUM NODE DISJOINT PATH COVERING FOR CIRCULAR-ARC GRAPHS [J].

BONUCCELLI, MA ;

BOVET, DP .

INFORMATION PROCESSING LETTERS, 1979, 8 (04) :159-161

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

BOOTH, KS ;

LUEKER, GS .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1976, 13 (03) :335-379

[4]

Garey M.R., 1979, COMPUTERS INTRACTABI, V174

[5]

Golumbic M. C., 1980, ALGORITHMIC GRAPH TH

[6] ADVANCES ON HAMILTONIAN COMPLETION PROBLEM [J].

GOODMAN, SE ;

HEDETNIEMI, ST .

JOURNAL OF THE ACM, 1975, 22 (03) :352-360

[7]

GOODMAN SE, 1974, GRAPH COMBINATOR, P262

[8] FINDING HAMILTONIAN CIRCUITS IN INTERVAL-GRAPHS [J].

KEIL, JM .

INFORMATION PROCESSING LETTERS, 1985, 20 (04) :201-206

[9]

MANACHER GK, IN PRESS INFORM PROC

[10]

MORAN S, IN PRESS THEORET COM

← 1 2 →