Documents in the NTIS Technical Reports collection are the results of federally funded research. They are directly submitted to or collected by NTIS from Federal agencies for permanent accessibility to industry, academia and the public.  Before purchasing from NTIS, you may want to check for free access from (1) the issuing organization's website; (2) the U.S. Government Printing Office's Federal Digital System website http://www.gpo.gov/fdsys; (3) the federal government Internet portal USA.gov; or (4) a web search conducted using a commercial search engine such as http://www.google.com.
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

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