Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/11042Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Nikolopoulos, S. | en |
| dc.contributor.author | Ioanninadou, K. | en |
| dc.date.accessioned | 2015-11-24T17:02:20Z | - |
| dc.date.available | 2015-11-24T17:02:20Z | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/11042 | - |
| dc.rights | Default Licence | - |
| dc.title | The Longest Path Problem is Polynomial on Cocomparability Graphs | en |
| heal.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.publicationDate | 2010 | - |
| heal.abstract | The longest path problem is the problem of ?nding a path of maximum length in a graph. As a generalization of the Hamiltonian path problem, it is NP-complete on general graphs and, in fact, on every class of graphs that the Hamiltonian path problem is NP-complete. Polynomial solutions for the longest path problem have recently been proposed for weighted trees, ptolemaic graphs, bipartite permutation graphs, interval graphs, and some small classes of graphs. Although the Hamiltonian path problem on cocomparability graphs was proved to be polynomial almost two decades ago [9], the complexity status of the longest path problem on cocomparability graphs has remained open until now; actually, the complexity status of the problem has remained open even on the smaller class of permutation graphs. In this paper, we present a polynomial-time algorithm for solving the longest path problem on the class of cocomparability graphs. Our result resolves the open question for the complexity of the problem on such graphs, and since cocomparability graphs form a superclass of both interval and permutation graphs, extends the polynomial solution of the longest path problem on interval graphs [18] and provides polynomial solution to the class of permutation graphs. | en |
| heal.journalName | Algorithmica | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά) | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| nikolopoulos-2011-The Longest Path Problem is Polynomial.pdf | 233.83 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
