loading...
On Parameterized Path and Chordless Path Problems
San Diego, California June 13-March 16
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2007.21Twenty-Second Annual IEEE Conference ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Yijia Chen, Jorg Flum, "On Parameterized Path and Chordless Path Problems," Computational Complexity, Annual IEEE Conference on, pp. 250-263, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), 2007.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2007.21,
author = {Yijia Chen and Jorg Flum},
title = {On Parameterized Path and Chordless Path Problems},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2007},
issn = {1093-0159},
pages = {250-263},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2007.21},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - On Parameterized Path and Chordless Path Problems
SN - 1093-0159
SP250
EP263
A1 - Yijia Chen,
A1 - Jorg Flum,
PY - 2007
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
Yijia Chen, Shanghai Jiaotong University, China
Jorg Flum, Universitat Freiburg, Germany
We study the parameterized complexity of various path (and cycle) problems, the parameter being the length of the path. For example, we show that the problem of the existence of a maximal path of length k in a graph G is fixed-parameter tractable, while its counting version is #W[1]- complete. The corresponding problems for chordless (or induced) paths are W[2]-complete and #W[2]-complete respectively. With the tools developed in this paper we derive the NP-completeness of a related classical problem, thereby solving a problem due to Hedetniemi [17].
Citation:
Yijia Chen, Jorg Flum, "On Parameterized Path and Chordless Path Problems," ccc, pp.250-263, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.