Skip to main content
SpringerLink
Log in

Parameterized and Exact Computation

Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008, Proceedings

  • Conference proceedings
  • © 2008

Overview

Editors:
  1. Martin Grohe
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Rolf Niedermeier
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 5018)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: IWPEC 2008.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (20 papers)

  1. Front Matter

    Download chapter PDF

  2. Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters

    • Jianer Chen
    Pages 1-8

  3. Algorithmic Graph Minors and Bidimensionality

    • Erik D. Demaine
    Pages 9-9

  4. Algorithmic Meta-theorems

    • Stephan Kreutzer
    Pages 10-12

  5. Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem

    • Omid Amini, Ignasi Sau, Saket Saurabh
    Pages 13-29

  6. Fixed Structure Complexity

    • Yonatan Aumann, Yair Dombb
    Pages 30-42

  7. An Improved Fixed-Parameter Algorithm for Minimum-Flip Consensus Trees

    • Sebastian Böcker, Quang Bao Anh Bui, Anke Truss
    Pages 43-54

  8. An O *(1.0977n) Exact Algorithm for max independent set in Sparse Graphs

    • Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos
    Pages 55-65

  9. New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem

    • Maw-Shang Chang, Chuang-Chieh Lin, Peter Rossmanith
    Pages 66-77

  10. Capacitated Domination and Covering: A Parameterized Perspective

    • Michael Dom, Daniel Lokshtanov, Saket Saurabh, Yngve Villanger
    Pages 78-90

  11. Some Fixed-Parameter Tractable Classes of Hypergraph Duality and Related Problems

    • Khaled Elbassioni, Matthias Hagen, Imran Rauf
    Pages 91-102

  12. A Purely Democratic Characterization of W[1]

    • Michael Fellows, Danny Hermelin, Moritz Müller, Frances Rosamond
    Pages 103-114

  13. Parameterized Complexity and Approximability of the SLCS Problem

    • Sylvain Guillemot
    Pages 115-128

  14. FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs

    • Sylvain Guillemot
    Pages 129-140

  15. Wheel-Free Deletion Is W[2]-Hard

    • Daniel Lokshtanov
    Pages 141-147

  16. Parameterized Derandomization

    • Moritz Müller
    Pages 148-159

  17. A Linear Kernel for Planar Feedback Vertex Set

    • Hans L. Bodlaender, Eelko Penninkx
    Pages 160-171

  18. Parameterized Chess

    • Allan Scott, Ulrike Stege
    Pages 172-189

  19. The Time Complexity of Constraint Satisfaction

    • Patrick Traxler
    Pages 190-201

  20. A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances

    • Magnus Wahlström
    Pages 202-213
Back to top

Keywords

About this book

This book constitutes the refereed proceedings of the Third International Workshop on Parameterized and Exact Computation, IWPEC 2008, held in Victoria, Canada, in May 2008 - co-located with the 40th ACM Symposium on Theory of Computing, STOC 2008. The 17 revised full papers presented together with 3 invited lectures were carefully reviewed and selected from 32 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 computation, implementation and experiments, high-performance computing and fixed-parameter tractability.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation