Open Access Open Access  Restricted Access Subscription Access

Decomposition of Dynamic Graphs in Memory Saving with Effective Programming

Rishabh Rauthan, Rohan Khaneja, Rohan Kadam, Swapnil Yadav

Abstract


This study proposes a simple and effective heuristic to save memory in effective programming on tree decompositions when solving a graph optimization problem. The introduced “anchor technique” is based on a tree-like set covering problem. We substantiated our findings by experimental results. Our strategy has negligible computational overhead concerning running time but achieves memory savings for nice tree decompositions and path decompositions between 60% and 98%.


Keywords


graph algorithms, tree decompositions of graphs, dynamic programming, set covering, memory usage

Full Text:

PDF

References


Alber J, Dorn F, Niedermeier R. Experimental evaluation of a tree

decomposition based algorithm for Vertex Cover on planar graphs. Discrete Applied Mathematics. 2005; 145(2): 219–31p.

Aspvall B, Proskurowski A, Telle JA. Memory requirements for table

computations in partial k-tree algorithms. Algorithmica. 2000; 27(3): 382–94p.

a). Bodlaender HL, Fomin FV. Tree decompositions with small cost. Discrete Applied Mathematics. 2005; 145(2): 143– 54p.b). Bodlaender HL. Treewidth: Algorithmic techniques and results. Proceedings of the 22nd International Symposium MFCS’97; 1997 Aug 25–29;

Bratislava, Slovakia. USA: Springer- Verlag; 1997. 19–36p. c). Bodlaender HL. A partial k-arboretum of graphs with bounded

treewidth. Theoretical Computer Science. 1998; 209: 1–45p. d). Bodlaender HL. Discovering treewidth. Proceedings of the 31st Conference on Current Trends in Theory and Practice of Computer Science SOFSEM; 2005 Jan 22–28; Liptovský Ján, Slovakia. USA: Springer-Verlag; 2005. 1– 16p. e). Bodlaender HL, Koster AMCA, van

den Eijkhof F. Pre-processing rules for triangulation of probabilistic networks. Technical Report. Utrecht University: Institute of Information and Computing Science; 2003.

Guo J, Niedermeier R. Exact algorithms and applications for Tree-like Weighted Set Cover. Journal of Discrete Algorithms. 2005; 4(4): 608–22p.

Page RDM, Cotton JA. Vertebrate phylogenomics: reconciled trees and gene duplications. Proceedings of the Pacific Symposium on Biocomputing; 2002 Jan 3–7; Lihue, Hawaii. 536–47p.

Tarjan RE, Yannakakis M. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing. 1984; 13(3): 566–79p.

Alber J, Betzler N, Niedermeier R. Experiments on data reduction for optimal domination in networks. Proceedings of the 1st International Network Optimization Conference (INOC); 2003 Oct; Paris, France. 1–6p (Long version to appear in Annals of Operations Research).

a) Amsterdam, Netherlands: Elsevier Science Publishers; 2001. d). Koster AMCA, van Hoesel SPM, Kolen AWJ. Solving Frequency Assignment Problems via Tree-decomposition. Electronic Notes in Discrete Mathematics.b). Mecke S, Wagner D. Solving geometric covering problems by data reduction. Proceedings of the 12th European Symposium on Algorithms (ESA); 2004 Sep 14–17; Bergen, Norway. USA: Springer-Verlag; 2004. 760–71p.

Song Y, Liu C, Malmberg R, et al. Tree decomposition based fast search of RNA structures including pseudoknots in genomes. Proceedings of the IEEE Computational Systems Bioinformatics Conference; 2005 Aug 8–11; Stanford University, California.

Alber J, Bodlaender HL, Fernau H, et al. Fixed parameter algorithms for Dominating Set and related problems on planar graphs. Algorithmica. 2002; 33(4): 461–93p.

Alber J, Niedermeier R. Improved tree decomposition based algorithms for domination-like problems. Proceedings of the 5th Latin American Symposium LATIN 2002: Theoretical Informatics; 2002 Apr 3–6; Cancun, Mexico. USA: Springer-Verlag; 2002. 613–27p.

a). Demaine ED, Hajiaghayi MT. Bidimensionality: new connections between FPT algorithms and PTASs. Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, SODA; 2005 Jan 23–25; Vancouver, BC, Canada. 590–601p. b). Fomin FV, Thilikos DM. Dominating sets in planar graphs: branch-width and exponential speed-up. Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms, SODA; 2003 Jan 12–14; Baltimore, Maryland. 168–77p.

a). Guo J, Niedermeier R, Raible D. Improved algorithms and complexity results for power domination in graphs. Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (FCT); 2005 Aug 17–20; Lübeck, Germany. USA: Springer-Verlag; 2005. 172–84p. b). Kloks T. Treewidth. Computations and Approximations. Lecture Notes in Computer Science, vol. 842. USA: Springer-Verlag; 1994. c). Koster AMCA, Bodlaender HL, Hoesel SPM. Treewidth: Computational Experiments. Electronic Notes in Discrete Mathematics. 14. Mehlhorn K, Näher S. LEDA: A Platform of Combinatorial and Geometric Computing. Cambridge, England: Cambridge University Press; 1999.


Refbacks

  • There are currently no refbacks.