Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Complexity of Canadian traveler problem variants
Stockholm University, Faculty of Science, Numerical Analysis and Computer Science (NADA). KTH Royal Inst Technol, SE-10044 Stockholm, Sweden.
2013 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 487, 1-16 p.Article in journal (Refereed) Published
Abstract [en]

The Canadian traveler problem (CTP) is the problem of traversing a given graph, where some of the edges may be blocked a state which is revealed only upon reaching an incident vertex. Originally stated by Papadimitriou and Yannakakis (1991) [1], the adversarial version of the CTP was shown to be PSPACE-complete, with the stochastic version shown to be in PSPACE and #P-hard. We show that the stochastic CTP is also PSPACE-complete: initially proving PSPACE-hardness for the dependent version of the stochastic CTP, and proceeding with gadgets that allow us to extend the proof to the independent case. Since for disjoint-path graphs, the CTP can be solved in polynomial time, we examine the complexity of the more general remote-sensing CTP, and show that it is NP-hard even for disjoint-path graphs.

Place, publisher, year, edition, pages
2013. Vol. 487, 1-16 p.
Keyword [en]
Canadian traveler problem, Complexity of navigation under uncertainty, Stochastic shortest path with recourse
National Category
Computer Science
Identifiers
URN: urn:nbn:se:su:diva-92020DOI: 10.1016/j.tcs.2013.03.016ISI: 000319791300001OAI: oai:DiVA.org:su-92020DiVA: diva2:637342
Funder
EU, European Research Council, 226203
Note

AuthorCount:4;

Available from: 2013-07-17 Created: 2013-07-15 Last updated: 2017-12-06Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text
By organisation
Numerical Analysis and Computer Science (NADA)
In the same journal
Theoretical Computer Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 38 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf