article · 2014
DIRECTED GRAPHS: FIXED-PARAMETER TRACTABILITY & BEYOND
Rajesh Chitnis
Cited by 0Abstract and details only
Abstract
Most interesting optimization problems on graphs are NP-hard, implying that (un-less P = NP) there is no polynomial time algorithm that solves all the instances of an NP-hard problem exactly. However, classical complexity measures the running time as a function of only the overall input size. The paradigm of parameterized complexity was introduced by Downey and Fellows to allow for a more refined multivariate analy-sis of the running time. In parameterized complexity, each problem comes along with a secondary measure k which is called the parameter. The goal of parameterized com-plexity is to design efficient algorithms for NP-hard problems when the parameter k is small, even if the input size is large. Formally, we say that a parameterized problem is fixed-parameter tractable (FPT) if instances of size n and parameter k can be solved in f (k) · nO(1) time, where f is a computable function which does not depend on n. A pa-rameterized problem belongs to the class XP if instances of size n and parameter k can be solved in f (k) ·nO(g(k)) time, where f and g are both computable functions. In this thesis we focus on the parameterized complexity of transversal and connec-tivity problems on directed graphs. This research direction has been hitherto relatively
Cite this paper
Chitnis, R. (2014). DIRECTED GRAPHS: FIXED-PARAMETER TRACTABILITY & BEYOND.
Chitnis, Rajesh. “DIRECTED GRAPHS: FIXED-PARAMETER TRACTABILITY & BEYOND.” 2014.
Chitnis, Rajesh. 2014. “DIRECTED GRAPHS: FIXED-PARAMETER TRACTABILITY & BEYOND.”
Chitnis, R. (2014) ‘DIRECTED GRAPHS: FIXED-PARAMETER TRACTABILITY & BEYOND’.
@article{chitnis2014directed,
title = {{DIRECTED GRAPHS: FIXED-PARAMETER TRACTABILITY & BEYOND}},
author = {Chitnis, Rajesh},
year = {2014}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.