On two techniques of combining branching and treewidth

DOI10.1007/s00453-007-9133-3zbMath1185.68475OpenAlexW2154399201WikidataQ60488698 ScholiaQ60488698MaRDI QIDQ1022343

Saket Saurabh, Fedor V. Fomin, Alexey A. Stepanov, Serge Gaspers

Publication date: 22 June 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9133-3

zbMATH Keywords

treewidthparameterized algorithmsexact exponential time algorithmsminimum maximal matching\(k\)-Weighted vertex cover\#3-Coloring\#minimum dominating setNP hard problems

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39)

Related Items (50)

Bounds on the maximum number of minimum dominating sets ⋮ Counting Maximal Independent Sets in Subcubic Graphs ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ On approximating (connected) 2-edge dominating set by a tree ⋮ A Multivariate Approach for Weighted FPT Algorithms ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Colorings with few colors: counting, enumeration and combinatorial bounds ⋮ An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set ⋮ A multivariate framework for weighted FPT algorithms ⋮ Space saving by dynamic algebraization based on tree-depth ⋮ New Results on Directed Edge Dominating Set ⋮ Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover} ⋮ Parameterized edge dominating set in graphs with degree bounded by 3 ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ New parameterized algorithms for the edge dominating set problem ⋮ Fast algorithms for max independent set ⋮ Exact algorithms for edge domination ⋮ Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract) ⋮ Bicolored independent sets and bicliques ⋮ Trimmed Moebius inversion and graphs of bounded degree ⋮ On partitioning a graph into two connected subgraphs ⋮ An improved parameterized algorithm for the independent feedback vertex set problem ⋮ A refined exact algorithm for edge dominating set ⋮ A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP ⋮ Parameterized Edge Dominating Set in Cubic Graphs ⋮ Fixed-parameter algorithms for Vertex Cover \(P_3\) ⋮ Maximum matching and kernelization of edge dominating set ⋮ The Asymmetric Travelling Salesman Problem In Sparse Digraphs. ⋮ Exact algorithms for minimum weighted dominating induced matching ⋮ Inclusion/exclusion meets measure and conquer ⋮ Parameterized measure \& conquer for problems with no small kernels ⋮ On Approximating (Connected) 2-Edge Dominating Set by a Tree ⋮ Partially Polynomial Kernels for Set Cover and Test Cover ⋮ Unnamed Item ⋮ Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds ⋮ Enumerate and Measure: Improving Parameter Budget Management ⋮ Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting ⋮ Dynamic parameterized problems ⋮ Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers ⋮ Finding and counting permutations via CSPs ⋮ Decomposition algorithms for solving the minimum weight maximal matching problem ⋮ Parameterized complexity of geometric covering problems having conflicts ⋮ Faster graph coloring in polynomial space ⋮ Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms ⋮ Exact algorithms for counting 3-colorings of graphs ⋮ Improving TSP Tours Using Dynamic Programming over Tree Decompositions. ⋮ New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enumerating maximal independent sets with applications to graph colouring.
• Refined memorization for vertex cover
• Pathwidth of cubic graphs and exact algorithms
• On generating all maximal independent sets
• A partial k-arboretum of graphs with bounded treewidth
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• A note on the complexity of minimum dominating set
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Vertex Cover: Further Observations and Further Improvements
• Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• Edge Dominating Sets in Graphs
• On efficient fixed-parameter algorithms for weighted vertex cover
• Parameterized and Exact Computation
• Algorithms for Counting 2-Sat Solutions and Colorings with Applications
• Branching and Treewidth Based Exact Algorithms
• STACS 2005
• Graph-Theoretic Concepts in Computer Science
• Automata, Languages and Programming
• Principles and Practice of Constraint Programming – CP 2003
• Graph-Theoretic Concepts in Computer Science
• Algorithms and Computation
• On cliques in graphs

This page was built for publication: On two techniques of combining branching and treewidth