Parameterized and Exact Computation

Name: Parameterized and Exact Computation | 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers

Dániel Marx Peter Rossmanith(Herausgeber*in)

Springer (Verlag)

Erschienen am 9. März 2012

VIII, 273 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-28050-4 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

7112
Preface
Organization
Table of Contents
On Multiway Cut Parameterized above Lower Bounds
Introduction
Algorithms for Multiway Cut
From Node Multiway Cut to Almost 2-SAT
Hardness of Node Multicut Parameterized above LP-Relaxation
Conclusions
References
Parameterized Complexity of Firefighting Revisited
Introduction
Saving and Protecting Vertices
W[1]-Hardness on General Graphs
Improved Algorithm on Trees
Tractability on Graphs of Bounded Treewidth
Burning Vertices
Algorithms
No Poly-kernel for Trees
Open Problems
References
Parameterized Complexity in Multiple-Interval Graphs: Domination
Introduction
Dominating Set
Connected Dominating Set, Independent Dominating Set, and Dominating Clique
Distance Dominating Set
Perfect Code
Distance Perfect Code
References
A Faster Algorithm for Dominating Set Analyzed by the Potential Method
Introduction
Definitions
Potential Method
Main Idea
Algorithm
Analysis
Exponential Space
Algorithm
Analysis
Conclusion
References
Contracting Graphs to Paths and Trees
Introduction
Definitions and Notation
Tree Contraction
Path Contraction
Concluding Remarks
References
Increasing the Minimum Degreeof a Graph by Contractions
Introduction
Preliminaries
Contractions
Weighted Contractions
Concluding Remarks
References
Planar Disjoint-Paths Completion
Introduction
Proof Strategy
Preliminaries
Bounding the Size of the Completion
The Algorithm for Planar-Dpc
The Enhancement Operation
The Stretching Lemma
Reducing PDPC to Topological Minor Testing
Further Extensions and Open Problems
References
Sparse Solutions of Sparse Linear Systems: Fixed-Parameter Tractability and an Application of Complex Group Testing
Introduction
Row-Sparse Linear Systems of Equations
A Problem Kernel for Binary Matrices
Sparse Nonnegative Solutions of Systems of Linear Inequalities via the Complex Model of Group Testing
Conclusions
References
New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree
Introduction
Problem Statement
The Main Definitions
Known Results
New Upper Bounds
Organization of the Paper
A Simple Algorithm for MAX-2-SAT and MAX-2-CSP
Removing Variables of Degree 2
An Algorithm
Going from the Maximal Degree to the Average Degree
An Algorithm for MAX-2-SAT and MAX-2-CSP
Further Directions
References
Improved Parameterized Algorithms for above Average Constraint Satisfaction
Introduction
Preliminaries
Max-c-Lin-2 above Average
Boolean MAX-c-CSP above Average
MAX-c-Permutation CSP above Average
References
On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal
Introduction
Preliminaries
Combinatorial Properties of Separators in Labeled Graphs
Polynomial Kernelization for (BIP Gtw(w))-OCT
Lower Bounds for Kernelization
Conclusion
Kernel Bounds for Path and Cycle Problems
Introduction
Preliminaries
A Property of Maximum Matchings in Bipartite Graphs
Polynomial Kernels for Path and Cycle Problems
Long Cycle Parameterized by a Vertex Cover
Other Path and Cycle Problems Parameterized by Vertex Cover
Parameterization by Max Leaf Number
Parameterization by a Modulator to Cluster Graphs
Lower Bounds for Path and Cycle Problems
Directed Hamiltonian Cycle with a Modulator to Bi-paths
Hamiltonian Cycle with a Modulator to Outerplanar Graphs
Finding Paths with Respect to Forbidden Pairs
Conclusion
References
On the Hardness of Losing Width
Introduction
? -Transversal Parameterized by Vertex Cover
Lower Bounds
Conclusions and Perspectives
References
Safe Approximation and Its Relation to Kernelization
Introduction
Preliminaries
Safe Approximation
Kernelization and Safe Approximation
Planar Dominating Set
Feedback Vertex Set
Multicut Problems
Conclusion
References
Simpler Linear-Time Kernelization for Planar Dominating Set
Introduction
Overview of the New Algorithm
Preliminaries
Definitions and Notation
Properties of Planar Graphs
Near-Twin Reduction
Description
Correctness
Execution Time
Reduction Progress
Shrinking Iterations
Description
Correctness
Execution Time
Reduction Progress
The Complete Algorithm
References
Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs
Introduction
Comparison to Previous Kernelizations
Data Reduction Rules
Private Neighborhood Rule
Joint Neighborhood Rule
Problem Kernel
Conclusion
References
Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width
Introduction
Definitions and Preliminary Results
Sparse and Dense k-Subgraph Problems
Algorithmic Upper Bounds for Sparse k-Subgraph
Lower Bounds
Degree-Constrained Subgraph Problems
Conclusion
References
Finding Good Decompositions for Dynamic Programming on Dense Graphs
Introduction
Boolean-Width
Heuristic Algorithm
Greedy Initialization
Local Search
Discussion and Implementation Details
Experimental Results
Small Grid Graphs
Conclusion
References
Parameterized Maximum Path Coloring
Introduction
Definitions and Preliminaries
Structural Parameterizations
Parameterizations Involving the Objective Function
Conclusions and Open Problems
References
On Cutwidth Parameterized by Vertex Cover
Introduction
Faster Cutwidth Parameterized by Vertex Cover
Kernelization Lower Bound
The Auxiliary Problem
No Polykernel for Hypergraph Minimum Bisection
From Hypergraph Minimum Bisection to Cutwidth
Conclusions
References
Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
Introduction
An FPT Algorithm for Graph Motif
Introducing Twin-Covers
Algorithms on Twin-Cover
Graph Motif
Equitable Coloring
Precoloring Extension
Boxicity
Additional algorithms
Monadic Second-Order Logic
MS1 on Graphs of Bounded Vertex Cover
MS1 on Graphs of Bounded Twin-Cover
Concluding notes
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken