The week's pick
Reseach Article
Comparative Analysis of Dynamic Graph Techniques and Data Structure
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 45 - Number 5 |
| Year of Publication: 2012 |
| Authors: Deepak Garg, Megha Tyagi |
10.5120/6779-9077
|
Deepak Garg, Megha Tyagi . Comparative Analysis of Dynamic Graph Techniques and Data Structure. International Journal of Computer Applications. 45, 5 ( May 2012), 41-46. DOI=10.5120/6779-9077
Abstract
Dynamically changing graphs are used in many applications of graph algorithms. The scope of these graphs are in graphics, communication networks and in VLSI designs where graphs are subjected to change, such as addition and deletion of edges and vertices. There is a rich body of the algorithms and data structures used for dynamic graphs. The paper overview the techniques and data structures used in various dynamic algorithms. The effort is tried to find out the comparison in these techniques namely the hierarchical decomposition of graphs and highlighting the ingenuity used in designing these algorithms.
References
- FREDERICKSON, G. N. 1985. Data structures for on- line updating of minimum spanning trees. SIAM J, 781–798.
- EPPSTEIN, D., GALIL, Z., ITALIANO, G. F., AND NISSENZWEIG, A. 1997. Sparsification–A technique for speeding up dynamic graph algorithms. J. ACM 44, 5 (Sept.), 669 – 696.
- Monika R. Henzinger and Valerie King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM 46(4) (1999), 502–516.
- GALIL, Z., AND ITALIANO, G. F. 1992. Fully dynamic algorithms for 2-edge connectivity. SIA J. Comput. 21, 1047–1069.
- D. D. Sleator, R. E. Tarjan, A Data Structure for DynamicTrees, Journal. Comput. Syst. Sci., 28(3):362- 391, 1983.
- HENZINGER, M. R. 1995. Fully dynamic biconnectivity in graphs. Algorithmica 13, 503–538.
- Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg,and Mikkel Thorup, Maintaining information in fully dynamic trees with top trees, ACM Transactions on Algorithms (TALG)
- Sauta Elisa Schaeffer, “Survey Graph clustering,” ElsevierComputer Science Review, vol. I, pp. 27-64, 2007
- Reena Mishra, Shashwat Shukla, Dr. Deepak Arora and Mohit Kumar. Article: An Effective Comparison of Graph Clustering Algorithms via Random Graphs. International Journal of Computer Applications 22(1):22–27, May 2011. Published by Foundation of Computer Science.
- G. W. Flake, R. E. Tarjan, and K. Tsioutsiouliklis. Graph clustering and minimum cut trees, Internet Mathematics, 1(3), 355-378, 2004.
- Mikkel Thorup: Near-optimal fully-dynamic graph connectivity. STOC 2000: 343-350
- Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup: Poly-logarithmic deterministic fullydynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48(4): 723-760 (2001).
- Mihai Patrascu, Erik D. Demaine: Lower bounds for dynamic connectivity. STOC 2004: 546-553.
- G. N. Frederickson. A data structure for dynamically maintaining rooted trees. Journal Of Algorithms, 24(1):37{65, 1997.
- U. A. Acar, G. E. Blelloch, and J. L. Vittes. An experimental analysis of change propagation in dynamic trees. pages 41{54, 2005.
- R. C. K. and S. Sudarshan. Graph clustering for keyword search. In COMAD ’ 09, 2009.
Index Terms
Keywords