A LINEAR TIME ALGORITHM FOR THE 1-FIXED-ENDPOINT PATH COVER PROBLEM ON INTERVAL GRAPHS

被引：13

作者：

Li, Peng ^{[1
,2
,3
]}

Wu, Yaokun ^{[1
,2
]}

机构：

[1] Shanghai Jiao Tong Univ, Dept Math, Shanghai 200240, Peoples R China

[2] Shanghai Jiao Tong Univ, MOE LSC, Shanghai 200240, Peoples R China

[3] Chongqing Univ Technol, Sch Math & Stat, Chongqing 400054, Peoples R China

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2017年 / 31卷 / 01期

基金：

中国国家自然科学基金;

关键词：

2-fixed-endpoint Hamiltonian path problem; forward degree sequence; Hamiltonian path; interval representation; normal vertex ordering; COCOMPARABILITY GRAPHS; POLYNOMIAL SOLUTION; RECOGNITION;

D O I：

10.1137/140981265

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Let G be an interval graph and take one of its vertices x. Can we find in linear time a minimum number of vertex disjoint paths of G which cover the vertex set of G and have x as one of their endpoints? This paper provides a positive answer to this problem. In the course of developing such an algorithm, we explore the possibility of getting insight on the path structure of interval graphs via greedy graph searches.

引用

页码：210 / 239

页数：30

共 18 条

[1] LINEAR ALGORITHM FOR OPTIMAL PATH COVER PROBLEM ON INTERVAL-GRAPHS [J].

ARIKATI, SR ;

RANGAN, CP .

INFORMATION PROCESSING LETTERS, 1990, 35 (03) :149-153

[2]

Asdre K, 2008, LECT NOTES COMPUT SC, V5059, P208

[3] The 1-Fixed-Endpoint Path Cover Problem is Polynomial on Interval Graphs [J].

Asdre, Katerina ;

Nikolopoulos, Stavros D. .

ALGORITHMICA, 2010, 58 (03) :679-710

[4] A polynomial solution to the k-fixed-endpoint path cover problem on proper interval graphs [J].

Asdre, Katerina ;

Nikolopoulos, Stavros D. .

THEORETICAL COMPUTER SCIENCE, 2010, 411 (7-9) :967-975

[5] 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

[6] Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs [J].

Broersma, Hajo ;

Fiala, Jiri ;

Golovach, Petr A. ;

Kaiser, Tomas ;

Paulusma, Daniel ;

Proskurowski, Andrzej .

JOURNAL OF GRAPH THEORY, 2015, 79 (04) :282-299

[7] LDFS-BASED CERTIFYING ALGORITHM FOR THE MINIMUM PATH COVER PROBLEM ON COCOMPARABILITY GRAPHS [J].

Corneil, Derek G. ;

Dalton, Barnaby ;

Habib, Michel .

SIAM JOURNAL ON COMPUTING, 2013, 42 (03) :792-807

[8] THE LBFS STRUCTURE AND RECOGNITION OF INTERVAL GRAPHS [J].

Corneil, Derek G. ;

Olariu, Stephan ;

Stewart, Lorna .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (04) :1905-1953

[9] PATHS IN INTERVAL-GRAPHS AND CIRCULAR ARC GRAPHS [J].

DAMASCHKE, P .

DISCRETE MATHEMATICS, 1993, 112 (1-3) :49-64

[10] The Longest Path Problem Is Polynomial on Cocomparability Graphs [J].

Ioannidou, Kyriaki ;

Nikolopoulos, Stavros D. .

ALGORITHMICA, 2013, 65 (01) :177-205

← 1 2 →