Tree decompositions of graphs: saving memory in dynamic programming

DOI10.1016/j.disopt.2006.05.008zbMath1128.68072OpenAlexW2154851838MaRDI QIDQ2465936

Johannes Uhlmann, Nadja Betzler, Rolf Niedermeier

Publication date: 11 January 2008

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2006.05.008

zbMATH Keywords

dynamic programminggraph algorithmsset coveringmemory usage(nice) tree decompositions of graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Efficient Problem Solving on Tree Decompositions Using Binary Decision Diagrams ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Complexity of finding maximum regular induced subgraphs with prescribed degree ⋮ Confronting intractability via parameters ⋮ Path cover problems with length cost

Uses Software

• LEDA
• BRITE

Cites Work

• Experiments on data reduction for optimal domination in networks
• Exact algorithms and applications for tree-like Weighted Set Cover
• A partial k-arboretum of graphs with bounded treewidth
• Treewidth. Computations and approximations
• Memory requirements for table computations in partial \(k\)-tree algorithms
• Tree decompositions with small cost
• Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Optimal Capacity Scheduling—I
• Solving partial constraint satisfaction problems with tree decomposition
• Practical algorithms on partial k-trees with an application to domination-like problems
• Algorithms – ESA 2004
• Fundamentals of Computation Theory
• SOFSEM 2005: Theory and Practice of Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Tree decompositions of graphs: saving memory in dynamic programming