Skip to main content
SpringerLink
Log in

Parameterized and Exact Computation

7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12-14, 2012. Proceedings

  • Conference proceedings
  • © 2012

Overview

Editors:
  1. Dimitrios M. Thilikos

    1. Department of Mathematics, National and Kapodistrian University of Athens, Athens, Greece

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Gerhard J. Woeginger

    1. Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, The Netherlands

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Up to date results
  • State of the art research
  • Fast track conference proceedings

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

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

Included in the following conference series:

Conference proceedings info: IPEC 2012.

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 54.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 72.00
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 (25 papers)

  1. Front Matter

    Download chapter PDF

  2. The Path Taken for k-Path

    • Andreas Björklund
    Pages 1-1

  3. Randomized Techniques for Parameterized Algorithms

    • Dániel Marx
    Pages 2-2

  4. Finding a Maximum Induced Degenerate Subgraph Faster Than 2n

    • Marcin Pilipczuk, Michał Pilipczuk
    Pages 3-12

  5. The Exponential Time Hypothesis and the Parameterized Clique Problem

    • Yijia Chen, Kord Eickmeyer, Jörg Flum
    Pages 13-24

  6. New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set

    • Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos, Mingyu Xiao
    Pages 25-36

  7. A New Algorithm for Parameterized MAX-SAT

    • Ivan Bliznets, Alexander Golovnev
    Pages 37-48

  8. Restricted and Swap Common Superstring: A Parameterized View

    • Paola Bonizzoni, Riccardo Dondi, Giancarlo Mauri, Italo Zoppis
    Pages 49-60

  9. Nonblocker in H-Minor Free Graphs: Kernelization Meets Discharging

    • Łukasz Kowalik
    Pages 61-72

  10. Some Definitorial Suggestions for Parameterized Proof Complexity

    • Jörg Flum, Moritz Müller
    Pages 73-84

  11. An Exact Algorithm for Subset Feedback Vertex Set on Chordal Graphs

    • Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Reza Saei
    Pages 85-96

  12. Preprocessing Subgraph and Minor Problems: When Does a Small Vertex Cover Help?

    • Fedor V. Fomin, Bart M. P. Jansen, Michał Pilipczuk
    Pages 97-108

  13. A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs

    • Cédric Bentz
    Pages 109-119

  14. Instance Compression for the Polynomial Hierarchy and beyond

    • Chiranjit Chakraborty, Rahul Santhanam
    Pages 120-134

  15. Polynomial Time and Parameterized Approximation Algorithms for Boxicity

    • Abhijin Adiga, Jasine Babu, L. Sunil Chandran
    Pages 135-146

  16. Homomorphic Hashing for Sparse Coefficient Extraction

    • Petteri Kaski, Mikko Koivisto, Jesper Nederlof
    Pages 147-158

  17. Fast Monotone Summation over Disjoint Sets

    • Petteri Kaski, Mikko Koivisto, Janne H. Korhonen
    Pages 159-170

  18. Weighted Counting of k-Matchings Is #W[1]-Hard

    • Markus Bläser, Radu Curticapean
    Pages 171-181

  19. Computing Directed Pathwidth in O(1.89n) Time

    • Kenta Kitsunai, Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki, Toshihiro Tano
    Pages 182-193

  20. MSOL Restricted Contractibility to Planar Graphs

    • James Abello, Pavel Klavík, Jan Kratochvíl, Tomáš Vyskočil
    Pages 194-205
Back to top

Other volumes

  1. Parameterized and Exact Computation

Keywords

About this book

This book constitutes the refereed proceedings of the 7th International Symposium on Parameterized and Exact Computation, IPEC 2012, in Ljubljana, Slovenia, in September 2012. The 21 revised full papers presented together with 2 keynote talks were carefully reviewed and selected from 37 submissions. The topics addressed cover research in all aspects of parameterized/exact algorithms and complexity including but are 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.

Editors and Affiliations

  • Department of Mathematics, National and Kapodistrian University of Athens, Athens, Greece

    Dimitrios M. Thilikos

  • Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, The Netherlands

    Gerhard J. Woeginger

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation