Index: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Home > Fixed-parameter algorithm

In computer science, fixed-parameter algorithms are an approach to attacking NP-hard problems. When trying to solve these problems exactly and deterministically, one has to deal with exponential running times; computational complexity theory indicates this is inevitable. Parameterized complexity theory accepts these exponential running times, but claims that not all “intractable” algorithms are equal, and some might even be feasible for practical applications.

The main idea is to consider parameters. Many problems have the following general form: given an object and a nonnegative integer , does have some property that depends on ? For instance, for Vertex Cover, the parameter can be the number of vertices in the cover. In many applications, for example when modelling error correction, one can assume the parameter to be “small” compared to the total input size. Then it is interesting to see whether we can find an algorithm which is exponential only in , and not in the input size.

In this way, parameterized complexity can be seen as two-dimensional complexity theory. This concept is formalized as follows:

A parameterized problem is a language , where is a finite alphabet. The second component is called the parameter of the problem.

A parameterized problem is fixed-parameter tractable if the question “?” can be decided in running time , where is an arbitrary function depending only on . The corresponding complexity class is called FPT.

For example there is an algorithm which solves Vertex Cover in time, where is the number of vertices and the size of the vertex cover. This proves that Vertex Cover is fixed-parameter tractable with respect to this parameter.

<Hide>

Topics: Fixed-parameter Algorithm, Fixed 3d, Fixed Point, Fixed Access...

Fixed 3dIn techniques for computer games, fixed 3D is a three-dimensional (3D) representation of the game world with game characters rendered in real time against a prerendered environment. Used heavily in the survival horror game genre, it was first seen in Info	Fixed pointIn mathematics, a fixed point of a function f is an argument x such that f ''x x see fixed point (mathematics). In physics, a fixed point usually describes a quantum field theory or a critical behavior of a model of statistical mechanics that is invariant	Fixed accessFixed access In personal communications service ( PCS), terminal access to a network in which there is a set relationship between a terminal and the access interface. Note: A single " identifier" serves for both the access interface and the terminal.
Fixed-wing aircraftFixed-wing aircraft is a term used to refer to monoplanes, biplanes and triplanes, in fact all conventional aircraft that are neither balloons, airships, autogyros, helicopters or tiltrotors. The term embraces a minority of aircraft that have folding wing	Fixed-odds gamblingFixed-odds gambling is a form of gambling against odds offered by a bookmaker, an individual, or on a bet exchange. It is customary with fixed-odds gambling to know the expected odds at the time of the placement of the wager (the "live price"), however th	Fixed point combinatorComputer science Lambda calculus Computability A fixed point combinator is a function which computes fixed points of other functions. A 'fixed point' of a function is a value left 'fixed' by that function; for example, 0 and 1 are fixed points of the squa
Fixed capital	Fixed (album)	Fixed-point lemma for normal functions
Fixed-point arithmetic	Fixed point (mathematics)	Fixed income
Fixed-rate bond	Fixed-parameter algorithm	Fixed shooter

Non User