Raman / Saurabh Parameterized and Exact Computation

5th International Symposium, IPEC 2010, Chennai, India, December 13-15, 2010. Proceedings
Erscheinungsjahr 2010
ISBN: 978-3-642-17493-3
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 239 Seiten, Web PDF

Reihe: Theoretical Computer Science and General Issues

Zielgruppe

Research

Autoren/Hrsg.

Raman, Venkatesh

Saurabh, Saket

Inhaltsverzeichnis

The Complexity of Satisfaction on Sparse Graphs.- Protrusions in Graphs and Their Applications.- Parameterized Complexity Results in Symmetry Breaking.- On the Kernelization Complexity of Colorful Motifs.- Partial Kernelization for Rank Aggregation: Theory and Experiments.- Enumerate and Measure: Improving Parameter Budget Management.- On the Exact Complexity of Evaluating Quantified k-CNF.- Cluster Editing: Kernelization Based on Edge Cuts.- Computing the Deficiency of Housing Markets with Duplicate Houses.- A New Lower Bound on the Maximum Number of Satisfied Clauses in Max-SAT and Its Algorithmic Application.- An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion.- Multivariate Complexity Analysis of Swap Bribery.- Parameterizing by the Number of Numbers.- Are There Any Good Digraph Width Measures?.- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems.- Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming.- On the Grundy Number of a Graph.- Exponential Time Complexity of Weighted Counting of Independent Sets.- The Exponential Time Complexity of Computing the Probability That a Graph Is Connected.- Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting.- Small Vertex Cover Makes Petri Net Coverability and Boundedness Easier.- Proper Interval Vertex Deletion.