Parameterized and Exact Computation
4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers
(Sprache: Englisch)
The Workshop on Parameterized and Exact Computation (IWPEC) is an - ternational workshop series that covers research in all aspects of parameterized and exact algorithms and complexity, and especially encourages the study of parameterized and exact...
Voraussichtlich lieferbar in 3 Tag(en)
versandkostenfrei
Buch (Kartoniert)
54.99 €
- Lastschrift, Kreditkarte, Paypal, Rechnung
- Kostenlose Rücksendung
- Ratenzahlung möglich
Produktdetails
Produktinformationen zu „Parameterized and Exact Computation “
Klappentext zu „Parameterized and Exact Computation “
The Workshop on Parameterized and Exact Computation (IWPEC) is an - ternational workshop series that covers research in all aspects of parameterized and exact algorithms and complexity, and especially encourages the study of parameterized and exact computations for real-world applications and algori- mic engineering. The goal of the workshop is to present recent research results, including signi?cant work-in-progress,and to identify and explore directions for future research. IWPEC2009wasthefourthworkshopintheseries,heldinCopenhagen,D- mark, during September 10-11, 2009. The workshop was part of ALGO 2009, which also hosted the 17th European Symposium on Algorithms (ESA 2009), the 9th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2009), and the 7th Workshop on Appr- imation and Online Algorithms (WAOA 2009). Three previous meetings of the IWPEC series were held in Bergen, Norway, 2004, Zu rich, Switzerland, 2006, and Victoria, Canada, 2008. At IWPEC 2009, we had two plenary speakers,Noga Alon (Tel Aviv Univ- sity, Israel) and Hans Bodlaender (Utrecht University, The Netherlands), giving 50-minutetalkseach.ProfessorAlonspokeon ColorCoding,BalancedHashing andApproximateCounting, andProfessorBodlaenderon Kernelization:New Upper and Lower Bound Techniques. Their respective abstracts accompanying the talks are included in these proceedings. InresponsetotheCallforPapers,52papersweresubmitted.Eachsubmission was reviewed by at least three reviewers (most by at least four). The reviewers were either Program Committee members or invited external reviewers. The ProgramCommittee held electronic meetings using the EasyChair system, went throughthoroughdiscussions,andselected25ofthesubmissionsforpresentation at the workshop and inclusion in this LNCS volume.
This book constitutes the refereed best selected papers of the 4th International Workshop on Parameterized and Exact Computation, IWPEC 2009, held in Copenhagen, Denmark, in September 2009.
The 25 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 52 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, parameterized complexity theory, relationship between parameterized complexity and traditional complexity classifications, applications of parameterized and exact computation, implementation issues of parameterized and exact algorithms, high-performance computing and fixed-parameter tractability.
The 25 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 52 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, parameterized complexity theory, relationship between parameterized complexity and traditional complexity classifications, applications of parameterized and exact computation, implementation issues of parameterized and exact algorithms, high-performance computing and fixed-parameter tractability.
Inhaltsverzeichnis zu „Parameterized and Exact Computation “
Balanced Hashing, Color Coding and Approximate Counting.- Kernelization: New Upper and Lower Bound Techniques.- A Faster Fixed-Parameter Approach to Drawing Binary Tanglegrams.- Planar Capacitated Dominating Set Is W[1]-Hard.- Boolean-Width of Graphs.- The Complexity of Satisfiability of Small Depth Circuits.- On Finding Directed Trees with Many Leaves.- Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms.- Pareto Complexity of Two-Parameter FPT Problems: A Case Study for Partial Vertex Cover.- What Makes Equitable Connected Partition Easy.- Improved Induced Matchings in Sparse Graphs.- Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs.- An Exact Algorithm for the Maximum Leaf Spanning Tree Problem.- An Exponential Time 2-Approximation Algorithm for Bandwidth.- On Digraph Width Measures in Parameterized Algorithmics.- The Parameterized Complexity of Some Geometric Problems in Unbounded Dimension.- Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms.- Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs.- A Probabilistic Approach to Problems Parameterized above or below Tight Bounds.- Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor.- Partitioning into Sets of Bounded Cardinality.- Two Edge Modification Problems without Polynomial Kernels.- On the Directed Degree-Preserving Spanning Tree Problem.- Even Faster Algorithm for Set Splitting!.- Stable Assignment with Couples: Parameterized Complexity and Local Search.- Improved Parameterized Algorithms for the Kemeny Aggregation Problem.- Computing Pathwidth Faster Than 2 n .
Bibliographische Angaben
- Autoren: Noga Alon , Sebastian Böcker , Rosa Enciso , Martin Fürer , Stefan Kratsch , Anders Yeo
- 2010, X, 335 Seiten, Maße: 15,6 x 23,8 cm, Kartoniert (TB), Englisch
- Herausgegeben: Jianer Chen, Fedor V. Fomin
- Verlag: Springer, Berlin
- ISBN-10: 3642112684
- ISBN-13: 9783642112683
- Erscheinungsdatum: 08.01.2010
Sprache:
Englisch
Kommentar zu "Parameterized and Exact Computation"
Schreiben Sie einen Kommentar zu "Parameterized and Exact Computation".
Kommentar verfassen