Branching and Treewidth Based Exact Algorithms

DOI10.1007/11940128_4MaRDI QIDQ5459098zbMATH OpenOpenAlexWikidataFDO

Authors Fedor V. Fomin, Serge Gaspers, Saket Saurabh

Publication date 24 April 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11940128_4

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On two techniques of combining branching and treewidth
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• On Exact Algorithms for Treewidth
• Faster algorithms on branch and clique decompositions
• On exact algorithms for treewidth

Cited in

(26)

• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• Improved approximation bounds for edge dominating set in dense graphs
• Constructive linear time algorithms for branchwidth
• An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set
• A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth
• Exact and heuristic algorithms for dynamic tree simplification
• On two techniques of combining branching and treewidth
• Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract)
• On the parameterized complexity of the acyclic matching problem
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• Parameterized algorithms for non-separating trees and branchings in digraphs
• Maximum minimal vertex cover parameterized by vertex cover
• On exact algorithms for treewidth
• Exact Algorithms for Edge Domination
• Parameterized approximation algorithms for weighted vertex cover
• Automata, Languages and Programming
• Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs
• New branch-and-bound algorithms for k-cardinality tree problems
• A multivariate approach for weighted FPT algorithms
• Read-Once Branching Programs for Tree Evaluation Problems
• Maximum minimal vertex cover parameterized by vertex cover
• A multivariate framework for weighted FPT algorithms
• Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth
• A new distributed approximation algorithm for the maximum weight independent set problem
• Parameterized approximation algorithms for weighted vertex cover

This page was built for publication: Branching and Treewidth Based Exact Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5459098)