This book constitutes the refereed proceedings of the First International Workshop on Parameterized and Exact Computation, IWPEC 2004, held in Bergen, Norway, in September 2004.
The 25 revised full papers presented together with an invited paper were carefully reviewed and selected from 47 submissions. The topics addressed focus on all current issues in this new approach to designing algorithms.
Author(s): Peter Damaschke (auth.), Rod Downey, Michael Fellows, Frank Dehne (eds.)
Series: Lecture Notes in Computer Science 3162
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2004
Language: English
Pages: 298
Tags: Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Data Structures; Discrete Mathematics in Computer Science; Algorithms
Front Matter....Pages -
Parameterized Enumeration, Transversals, and Imperfect Phylogeny Reconstruction....Pages 1-12
Online Problems, Pathwidth, and Persistence....Pages 13-24
Chordless Paths Through Three Vertices....Pages 25-36
Computing Small Search Numbers in Linear Time....Pages 37-48
Bounded Fixed-Parameter Tractability: The Case 2 poly( k) ....Pages 49-60
Refined Memorisation for Vertex Cover....Pages 61-70
Parameterized Graph Separation Problems....Pages 71-82
Parameterized Coloring Problems on Chordal Graphs....Pages 83-95
On Decidability of MSO Theories of Representable Matroids....Pages 96-107
On Miniaturized Problems in Parameterized Complexity Theory....Pages 108-120
Smaller Kernels for Hitting Set Problems of Constant Arity....Pages 121-126
Packing Edge Disjoint Triangles: A Parameterized View....Pages 127-137
Looking at the Stars....Pages 138-148
Moving Policies in Cyclic Assembly-Line Scheduling....Pages 149-161
A Structural View on Parameterizing Problems: Distance from Triviality....Pages 162-173
Perfect Path Phylogeny Haplotyping with Missing Data Is Fixed-Parameter Tractable....Pages 174-186
Simplifying the Weft Hierarchy....Pages 187-199
The Minimum Weight Triangulation Problem with Few Inner Points....Pages 200-212
A Direct Algorithm for the Parameterized Face Cover Problem....Pages 213-222
On Finding Short Resolution Refutations and Small Unsatisfiable Subsets....Pages 223-234
Parameterized Algorithms for Feedback Vertex Set....Pages 235-247
Automated Proofs of Upper Bounds on the Running Time of Splitting Algorithms....Pages 248-259
Improved Parameterized Algorithms for Feedback Set Problems in Weighted Tournaments....Pages 260-270
Greedy Localization, Iterative Compression, and Modeled Crown Reductions: New FPT Techniques, an Improved Algorithm for Set Splitting , and a Novel 2 k Kernelization for Vertex Cover ....Pages 271-280
Space and Time Complexity of Exact Algorithms: Some Open Problems....Pages 281-290
Practical FPT Implementations and Applications....Pages 291-291
Back Matter....Pages -
