Graph-Theoretic Concepts in Computer Science

DOI10.1007/B93953MaRDI QIDQ5902506zbMATH OpenFDO

Authors Michael R. Fellows

Publication date 12 January 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/B93953

zbMATH Keywords

survey paperparameterized complexitygraph problemsFPT algorithmsproblem reduction

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited in

(30)

• Exact algorithms and applications for tree-like Weighted Set Cover
• Fixed-parameter tractability and data reduction for multicut in trees
• Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters
• Kernels for storage capacity and dual index coding
• Crown reductions for the minimum weighted vertex cover problem
• The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT
• Looking at the stars
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Improved upper bounds for vertex cover
• Linear kernelizations for restricted 3-Hitting Set problems
• Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
• Win-win kernelization for degree sequence completion problems
• A 2k-kernelization algorithm for vertex cover based on crown decomposition
• Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
• Preprocessing to reduce the search space: antler structures for feedback vertex set
• What Is Known About Vertex Cover Kernelization?
• Subexponential parameterized algorithms
• A \(5k\)-vertex kernel for \(P_2\)-packing
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Parameterized computation and complexity: a new approach dealing with NP-hardness
• Preprocessing to reduce the search space for odd cycle transversal
• Baby PIH: Parameterized inapproximability of min CSP
• Preprocessing to reduce the search space: antler structures for feedback vertex set
• A fixed-parameter tractability result for multicommodity demand flow in trees
• Parameterized inapproximability hypothesis under ETH
• Structural properties of hard metric TSP inputs (extended abstract)
• Kernels for packing and covering problems
• The complexity ecology of parameters: An illustration using bounded max leaf number
• The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
• A Fast Approximation Scheme for the Multiple Knapsack Problem

This page was built for publication: Graph-Theoretic Concepts in Computer Science

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5902506)