Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth

DOI10.1007/978-3-642-39206-1_17zbMath1296.68074OpenAlexW2180988813WikidataQ59567500 ScholiaQ59567500MaRDI QIDQ5326561

Marek Cygan, Jesper Nederlof, Stefan Kratsch, Hans L. Bodlaender

Publication date: 6 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://dspace.library.uu.nl/handle/1874/303216

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (20)

New analysis and computational study for the planar connected dominating set problem ⋮ Hitting forbidden subgraphs in graphs of bounded treewidth ⋮ Linear kernels for outbranching problems in sparse digraphs ⋮ Deterministic Algorithms for the Independent Feedback Vertex Set Problem ⋮ Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Solving SCS for bounded length strings in fewer than \(2^n\) steps ⋮ Algebraic methods in the congested clique ⋮ Faster deterministic \textsc{Feedback Vertex Set} ⋮ A $c^k n$ 5-Approximation Algorithm for Treewidth ⋮ The role of planarity in connectivity problems parameterized by treewidth ⋮ Unnamed Item ⋮ Contraction-Bidimensionality of Geometric Intersection Graphs ⋮ Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth ⋮ An improved exact algorithm for TSP in graphs of maximum degree 4 ⋮ An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure ⋮ Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter

This page was built for publication: Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth