Output details
11 - Computer Science and Informatics
University of Durham
Article title
A simple polynomial algorithm for the longest path problem on cocomparability graphs
Type
D - Journal article
Title of journal
SIAM Journal on Discrete Mathematics
Article number
-
Volume number
26
Issue number
3
First page of article
940
ISSN of journal
0895-4801
Year of publication
2012
Number of additional authors
1
Additional information
<13>This is the first paper where the technique of applying a Lexicographic Depth First Search (LDFS) preprocessing to the vertices of a graph has been used to prove that a computationally hard combinatorial problem (in this case, the longest path problem) is polynomial time solvable on a specific graph class (in this case, cocomparability graphs). This powerful technique has inspired the paper [Corneil, Dalton, Habib, SIAM Journal on Computing, 42(3), 2013, pages 792–807] which appeared (almost) concurrently and independently of our work. Our paper and this paper cross-reference each other.
Interdisciplinary
-
Cross-referral requested
-
Research group
A - Algorithms and Complexity Research Group
Citation count
2
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
