|
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
Decomposition
Dynamic programming
Graphs
Heuristics
Implementation
Optimization
Polynomials
|
|
|
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
|
