| Description |
1 online resource (viii, 271 pages) |
| Series |
Lecture notes in computer science, 0302-9743 ; 7112 |
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues |
|
Lecture notes in computer science ; 7112.
|
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
|
| Contents |
On Multiway Cut Parameterized above Lower Bounds / Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk and Jakub Onufry Wojtaszczyk -- Parameterized Complexity of Firefighting Revisited / Marek Cygan, Fedor V. Fomin and Erik Jan van Leeuwen -- Parameterized Complexity in Multiple-Interval Graphs: Domination / Minghui Jiang and Yong Zhang -- A Faster Algorithm for Dominating Set Analyzed by the Potential Method / Yoichi Iwata -- Contracting Graphs to Paths and Trees / Pinar Heggernes, Pim van 't Hof, Benjamin Lévêque, Daniel Lokshtanov and Christophe Paul -- Increasing the Minimum Degree of a Graph by Contractions / Petr A. Golovach, Marcin Kamiński, Daniël Paulusma and Dimitrios M. Thilikos -- Planar Disjoint-Paths Completion / Isolde Adler, Stavros G. Kolliopoulos and Dimitrios M. Thilikos -- Sparse Solutions of Sparse Linear Systems: Fixed-Parameter Tractability and an Application of Complex Group Testing / Peter Damaschke -- New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree / Alexander Golovnev -- Improved Parameterized Algorithms for above Average Constraint Satisfaction / Eun Jung Kim and Ryan Williams -- On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal / Bart M.P. Jansen and Stefan Kratsch -- Kernel Bounds for Path and Cycle Problems / Hans L. Bodlaender, Bart M.P. Jansen and Stefan Kratsch -- On the Hardness of Losing Width / Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk and Saket Saurabh -- Safe Approximation and Its Relation to Kernelization / Jiong Guo, Iyad Kanj and Stefan Kratsch -- Simpler Linear-Time Kernelization for Planar Dominating Set / Torben Hagerup -- Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs / René van Bevern, Sepp Hartung, Frank Kammer, Rolf Niedermeier and Mathias Weller -- Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width / Hajo Broersma, Petr A. Golovach and Viresh Patel -- Finding Good Decompositions for Dynamic Programming on Dense Graphs / Eivind Magnus Hvidevold, Sadia Sharmin, Jan Arne Telle and Martin Vatshelle -- Parameterized Maximum Path Coloring / Michael Lampis -- On Cutwidth Parameterized by Vertex Cover / Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk and Saket Saurabh -- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics / Robert Ganian |
| Summary |
This book constitutes the thoroughly refereed post-conference proceedings of the 6th International Symposium on Parameterized and Exact Computation, IPEC 2011, in Saarbrücken, Germany, in September 2011. The 21 revised full papers presented were carefully reviewed and selected from 40 submissions. The topics addressed cover research in all aspects of parameterized and exact computation and complexity, including but not limited to new techniques for the design and analysis of parameterized and exact algorithms, fixed-parameter tractability results, parameterized complexity theory, relationship between parameterized complexity and traditional complexity classifications, applications of parameterized and exact computation, and implementation issues of parameterized and exact algorithms |
| Analysis |
Computer science |
|
Information theory |
|
Computer software |
|
Computational complexity |
|
Algebra -- Data processing |
|
Algorithms |
|
Algorithm Analysis and Problem Complexity |
|
Discrete Mathematics in Computer Science |
|
Theory of Computation |
|
Symbolic and Algebraic Manipulation |
|
Computation by Abstract Devices |
| Bibliography |
Includes bibliographical references and author index |
| Subject |
Parameter estimation -- Congresses
|
|
Computer algorithms -- Congresses
|
|
Computational complexity -- Congresses
|
|
Informatique.
|
|
Computational complexity
|
|
Computer algorithms
|
|
Parameter estimation
|
| Genre/Form |
Conference papers and proceedings
|
|
Software.
|
| Form |
Electronic book
|
| Author |
Marx, Dániel
|
|
Rossmanith, Peter
|
| ISBN |
9783642280504 |
|
3642280501 |
|
