Accession Number DE2012-1055043
Title INDDGO: Integrated Network Decomposition and Dynamic Programming for Graph Optimization.
Publication Date Oct 2012
Media Count 34p
Personal Author B. D. Sullivan C. S. Groer D. P. Weerapurage
Abstract It is well-known that dynamic programming algorithms can utilize tree decompositions to provide a way to solve some NP-hard graph optimization problems where the complexity is polynomial in the number of nodes and edges in the graph, but exponential in the width of the underlying tree decomposition. However, there has been relatively little computational work done to determine the practical utility of such dynamic programming algorithms. We have developed software to construct tree decompositions using various heuristics and have created a fast, memory-efficient dynamic programming implementation for solving maximum weighted independent set. We describe our software and the algorithms we have implemented, focusing on memory saving techniques for the dynamic programming. We compare the running time and memory usage of our implementation with other techniques for solving maximum weighted independent set, including a commercial integer programming solver and a semi-denite programming solver. Our results indicate that it is possible to solve some instances where the underlying decomposition has width much larger than suggested by the literature. For certain types of problems, our dynamic programming code runs several times faster than these other methods.
Keywords Algorithms
Computer networks
Dynamic programming

Source Agency Technical Information Center Oak Ridge Tennessee
NTIS Subject Category 62B - Computer Software
45C - Common Carrier & Satellite
Corporate Author Oak Ridge National Lab., TN.
Document Type Technical report
Title Note N/A
NTIS Issue Number 1308
Contract Number DE-AC05-00OR22725

Science and Technology Highlights

See a sampling of the latest scientific, technical and engineering information from NTIS in the NTIS Technical Reports Newsletter

Acrobat Reader Mobile    Acrobat Reader