Logo - springer
Slogan - springer

Computer Science - Software Engineering | Parameterized and Exact Computation - 4th International Workshop, IWPEC 2009, Copenhagen, Denmark,

Parameterized and Exact Computation

4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers

Chen, Jianer, Fomin, Fedor V. (Eds.)


Available Formats:

Springer eBooks may be purchased by end-customers only and are sold without copy protection (DRM free). Instead, all eBooks include personalized watermarks. This means you can read the Springer eBooks across numerous devices such as Laptops, eReaders, and tablets.

You can pay for Springer eBooks with Visa, Mastercard, American Express or Paypal.

After the purchase you can directly download the eBook file or read it online in our Springer eBook Reader. Furthermore your eBook will be stored in your MySpringer account. So you can always re-download your eBooks.


(net) price for USA

ISBN 978-3-642-11269-0

digitally watermarked, no DRM

Included Format: PDF

download immediately after purchase

learn more about Springer eBooks

add to marked items


Softcover (also known as softback) version.

You can pay for Springer Books with Visa, Mastercard, American Express or Paypal.

Standard shipping is free of charge for individual customers.


(net) price for USA

ISBN 978-3-642-11268-3

free shipping for individuals worldwide

usually dispatched within 3 to 5 business days

add to marked items

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.

Content Level » Research

Keywords » algorithmics - algorithms - classification - complexity - computational graph theory - discrete mathematic - exponential time - graph algorithms - maximum spanning tree - optimization - parametrized algorithms - parametrized complexity - satisfiability - sparse graphs - vertex cover

Related subjects » Computational Science & Engineering - Software Engineering - Theoretical Computer Science

Table of contents 

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 .

Popular Content within this publication 



Read this Book on Springerlink

Services for this book

New Book Alert

Get alerted on new Springer publications in the subject area of Programming Techniques.