NDLI: Review of Parameterized Complexity by R. Downey and M. Fellows

Please wait, while we are loading the content...

Volume 31, Issue 4, Dec. 2000

The Book Review Column

Reviews of THREE books on Fair Division of Resources

Review of Computational Geometry: Algorithms and Applications (2nd ed.) by Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf

Review of Parameterized Complexity by R. Downey and M. Fellows

Review of: Modern Graph Theory by Béla Bollobás

Review of $A=B^{5}$ by Marko Petkovsek, Herbert S. Wilf, and Doron Zeilberger

Review of Communicating and mobile systems

Reprints from Computing Reviews

NSF Report: Theory of Computing Program

A moment of perfect clarity II

Principles of distributed computing

Computational geometry column 40

Going Backwards

Report on the 6th international meeting on DNA-based computers

Half century of automata theory

Death of a monster

Volume 31, Issue 3, Sept. 2000

Volume 31, Issue 2, June 1 2000

Volume 31, Issue 1, March 2000

Issue 14, January 1972

Issue 13, December 1971

Issue 12, October 1971

Issue 11, August 1971

Issue 10, July 1971

Issue 9, April 1971

Issue 8, January 1971

Issue 7, September 1970

Issue 6, June 1970

Issue 4, January 1970

Issue 3, October 1969

Issue 2, July 1969

Issue 1, April 1969

Review of Parameterized Complexity by R. Downey and M. Fellows

Content Provider	ACM Digital Library
Author	Istrate, Gabriel
Abstract	One of the most pervasive critiques of Computational Complexity, coming from the applied Computer Science community, is that it is an abstract, largely irrelevant field, that fails to capture the various intuitions concerning the complexity of "real-world" instances they have gathered through experiments. One aspect of these intuitions is that while most problems of practical interest tend to be intractable from a standard complexity-theoretic point of view, in many cases such problems have natural "structural" parameters, and practically relevant instances are often associated with "small" values of these parameters.Parameterized Complexity is an extension of Complexity Theory that attempts to formalize and deal with this intuition. It has already been applied to fields such as Databases, Logic and Constraint Programming, Computational Biology, Nonmonotonic Reasoning, Natural Language Processing, Cognitive Science, and Robotics. Some of its ideas have even been discovered independently by practitioners working in these areas. We do not attempt a further presentation (the interested reader can consult two excellent surveys [DF99, DFS99]), but want to illustrate this point through a revealing example: it has long been known that the register-allocation problem for imperative programming language amounts to a coloring problem on the associated control-flow graph, thus it seems, at a first glance, hard even in an approximate sense. On the other hand Thorup [Th98] has shown that such graphs are characterized by a bounded value (at most 10) of an intrinsic parameter called treewidth, that guarantees the existence of an approximation algorithm with substantially better performance than the one available for general graphs.The present book is an attempt to a first presentation of this emerging area by two of its most active proponents.
Starting Page	13
Ending Page	15
Page Count	3
File Format	PDF
ISSN	01635700
DOI	10.1145/369836.571191
Journal	ACM SIGACT News (SIGA)
Volume Number	31
Issue Number	4
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1992-06-30
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in