Parameterized and Exact Computation

Inhaltsverzeichnis

• 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.