Király, Zoltán (2014) Shortest paths in nearly conservative digraphs. In: Parameterized and Exact Computation. Lecture Notes in Computer Science (8894). Springer International Publishing Switzerland, Cham, pp. 234-245. ISBN 978-3-319-13523-6
|
Text
ShortestPath.pdf Download (158kB) | Preview |
Abstract
We introduce the following notion: a digraph D = (V, A) with arc weights c: A → R is called nearly conservative if every negative cycle consists of two arcs. Computing shortest paths in nearly conservative digraphs is NP-hard, and even deciding whether a digraph is nearly conservative is coNP-complete. We show that the “All Pairs Shortest Path” problem is fixed parameter tractable with various parameters for nearly conservative digraphs. The results also apply for the special case of conservative mixed graphs.
| Item Type: | Book Section |
|---|---|
| Uncontrolled Keywords: | Directed graphs; Shortest path; NP-hard; FPT algorithms; bioinformatics; Artificial intelligence; Mixed graph; FPT algorithm; Conservative weights; All Pairs Shortest Paths |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 26 Jan 2015 13:22 |
| Last Modified: | 26 Jan 2015 13:22 |
| URI: | http://real.mtak.hu/id/eprint/20953 |
Actions (login required)
 |
Edit Item |
