Concepedia

Fpt Approximation Algorithms

FPT Approximation Algorithm is an algorithmic paradigm within parameterized complexity theory that, for a given optimization problem parameterized by a specific parameter, computes an approximate solution in time bounded by a function of the parameter multiplied by a polynomial in the input size, thereby distinguishing itself from classical approximation algorithms by allowing the approximation ratio and runtime dependence on the parameter to be decoupled.

69

Publications

2.3K

Citations

148

Authors

88

Institutions

Publications per year

2017–2026

30

Parents

Publications

69

Bidimensionality: new connections between FPT algorithms and PTASs

Erik D. Demaine, MohammadTaghi Hajiaghayi · 2005 · 145 citations

, , +16

Branch-and-reduce exponential/FPT algorithms in practice: A case study of vertex cover

Takuya Akiba, Yoichi Iwata · Theoretical Computer Science · 2015 · 120 citations

, , +13

Short Cycles Make W-hard Problems Hard: FPT Algorithms for W-hard Problems in Graphs with no Short Cycles

Venkatesh Raman, Saket Saurabh · Algorithmica · 2008 · 114 citations

, , +12

An O(2O(k)n3) FPT Algorithm for the Undirected Feedback Vertex Set Problem

Frank Dehne, Michael R. Fellows, Michael A. Langston et al. · Theory of Computing Systems · 2007 · 104 citations

, , +9

Scalable Parallel Algorithms for FPT Problems

Faisal N. Abu-Khzam, Michael A. Langston, Pushkar Shanbhag et al. · Algorithmica · 2006 · 80 citations · Full text

, , +11

1–5 of 69

Authors

148

  1. SS
    Saket Saurabh

    Institute of Mathematical Sciences, India

    6 publications · 220 citations

    6

    h-index

  2. MC
    Marek Cygan

    University of Warsaw, Poland

    5 publications · 176 citations

    5

    h-index

  3. PS
    Piotr Skowron

    University of Warsaw, Poland

    5 publications · 107 citations

    5

    h-index

  4. PF
    Piotr Faliszewski

    AGH University of Krakow, Poland

    5 publications · 132 citations

    5

    h-index

  5. YI
    Yoichi Iwata

    The University of Tokyo, Japan

    4 publications · 267 citations

    4

    h-index

1–5 of 148

Institutions

88

  1. University of Bergen

    Bergen, Norway

    11 h-index

    25 publications

    458 citations

  2. University of Warsaw

    Warsaw, Poland

    8 h-index

    17 publications

    668 citations

  3. Institute of Mathematical Sciences

    Chennai, India

    7 h-index

    15 publications

    529 citations

  4. Ben-Gurion University of the Negev

    Beersheba, Israel

    5 h-index

    5 publications

    95 citations

  5. AGH University of Krakow

    Krakow, Poland

    4 h-index

    4 publications

    104 citations

  6. The University of Tokyo

    Tokyo, Japan

    4 h-index

    6 publications

    341 citations

  7. Carnegie Mellon University

    Pittsburgh, United States

    3 h-index

    3 publications

    75 citations

  8. University of Maryland, College Park

    College Park, United States

    3 h-index

    6 publications

    220 citations

1–8 of 88

Venues

  1. DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

    Repository · 8 publications · 133 citations

    8

    h-index

  2. Algorithmica

    7 publications · 324 citations

    7

    h-index

  3. Theoretical Computer Science

    5 publications · 182 citations

    5

    h-index

  4. SIAM Journal on Computing

    4 publications · 176 citations

    4

    h-index

  5. Information Processing Letters

    4 publications · 103 citations

    4

    h-index

1–5