Parameterized and exact computation : 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised selected papers / edited by Dániel Marx, Peter Rossmanith.

By: (6th : IPEC (Symposium) (6th : 2011 : Saarbrücken, Germany)
Contributor(s): Marx, Dániel | Rossmanith, Peter
Material type: TextTextSeries: SerienbezeichnungLecture notes in computer science: 7112.; LNCS sublibrary: Publisher: Berlin ; New York : Springer, ©2012Description: 1 online resource (viii, 271 pages)Content type: text Media type: computer Carrier type: online resourceISBN: 9783642280504; 3642280501Subject(s): Parameter estimation -- Congresses | Computer algorithms -- Congresses | Computational complexity -- Congresses | Informatique | Computational complexity | Computer algorithms | Parameter estimation | 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 DevicesGenre/Form: Electronic books. | Conference papers and proceedings. | Computer software. Additional physical formats: Printed edition:: No titleDDC classification: 511.352 LOC classification: QA267.8 | .I96 2011Online resources: Click here to access online
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.
Tags from this library: No tags from this library for this title. Log in to add tags.
    Average rating: 0.0 (0 votes)
Item type Current location Collection Call number Status Date due Barcode Item holds
eBook eBook e-Library

Electronic Book@IST

EBook Available
Total holds: 0

Includes bibliographical references and author index.

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.

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.

There are no comments for this item.

to post a comment.

Powered by Koha