scientific article; zbMATH DE number 2086260

MaRDI QIDQ3044360zbMATHFDO

Authors Jochen Alber, Rolf Niedermeier

Publication date 11 August 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2286/22860613.htm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Practical algorithms on partial k-trees with an application to domination-like problems
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Faster algorithms on branch and clique decompositions
• Dynamic programming and planarity: improved tree-decomposition based algorithms
• The Fine Details of Fast Dynamic Programming over Tree Decompositions

Cited in

(29)

• The complexity ecology of parameters: An illustration using bounded max leaf number
• Courcelle's theorem -- a game-theoretic approach
• Fast Algorithms for Join Operations on Tree Decompositions
• scientific article; zbMATH DE number 7278055 (Why is no real title available?)
• Tree decompositions of graphs: saving memory in dynamic programming
• Practical algorithms on partial k-trees with an application to domination-like problems
• Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
• Improved algorithms and complexity results for power domination in graphs
• Weighted maximum-clique transversal sets of graphs
• How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms
• Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
• Dynamic programming and planarity: improved tree-decomposition based algorithms
• Counting Maximal Independent Sets in Subcubic Graphs
• Two Birds with One Stone: The Best of Branchwidth and Treewidth with One Algorithm
• The parameterized complexity of the induced matching problem
• Star partitions on graphs
• Dual parameterization and parameterized approximability of subset graph problems
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Optimal dynamic program for \(r\)-domination problems over tree decompositions
• A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
• On the \(k\)-rainbow domination in graphs with bounded tree-width
• Graph minors and parameterized algorithm design
• Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm
• Graphs, branchwidth, and tangles! Oh my!
• On independent sets and bicliques in graphs
• Tree-decompositions of small pathwidth
• Branch decompositions and minor containment
• Structural parameters, tight bounds, and approximation for \((k, r)\)-center
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors

Describes a project that uses

Uses Software

• LEDA

This page was built for publication:

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