A Linear Time Algorithm for Computing Longest Paths in 2-Trees

被引：0

作者：

Markov, Minko ^{[1
]}

Vassilev, Tzvetalin S. ^{[2
]}

Manev, Krassimir ^{[1
]}

机构：

[1] Sofia Univ St Kliment Ohridski, Fac Math & Informat, Dept Comp Syst, BG-1164 Sofia, Bulgaria

[2] Nipissing Univ, Dept Comp Sci & Math, North Bay, ON P1B 8L7, Canada

来源：

ARS COMBINATORIA | 2013年 / 112卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

algorithmic graph theory; longest path; treewidth; 2-tree; LENGTH; GRAPH;

D O I：

暂无

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We propose a practical linear time algorithm for the LONGEST PATH problem on 2-trees.

引用

页码：329 / 351

页数：23

共 14 条

[1] COLOR-CODING [J].

ALON, N ;

YUSTER, R ;

ZWICK, U .

JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 1995, 42 (04) :844-856

[2]

[Anonymous], 1979, COMPUTERS INTRACTABI

[3] Finding a path of superlogarithmic length [J].

Björklund, A ;

Husfeldt, T .

SIAM JOURNAL ON COMPUTING, 2003, 32 (06) :1395-1402

[4]

Bodlaender Hans L., 1996, SIAM J COMPUT, V25, P1305

[5]

Bodlaender Hans L., 1993, J ALGORITHMS, V14, P1

[6] On computing a longest path in a tree [J].

Bulterman, RW ;

van den Sommen, FW ;

Zwaan, G ;

Verhoeff, T ;

van Gasteren, AJM ;

Feijen, WHJ .

INFORMATION PROCESSING LETTERS, 2002, 81 (02) :93-96

[7]

Dorn F, 2008, PROCEEDINGS OF THE NINETEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P631

[8]

Gabow HN, 2008, LECT NOTES COMPUT SC, V5369, P752, DOI 10.1007/978-3-540-92182-0_66

[9] On approximating the longest path in a graph [J].

Karger, D ;

Motwani, R ;

Ramkumar, GDS .

ALGORITHMICA, 1997, 18 (01) :82-98

[10]

Markov M., 2012, SERDICA J COMPUT, V6, P287

← 1 2 →