ST: Advanced Algorithms for Graphs and Networks - CS 6/79995

(Research oriented Course)

Spring 2009

MW 2:15 pm - 3:30 pm,  MSB 276

Instructor
Office Hours   
   
      
Email 
Telephone

Dr. Feodor Dragan 
Room 254 MSB
MW 1:45 – 2:15  PM, M 3:30 – 5:00 pm  
and by appointment 
dragan at cs kent edu
(330)  672-9058

Final grades:  http://www.cs.kent.edu/~dragan/ST/ST-Grades.pdf

Student Presentations Schedule http://www.cs.kent.edu/~dragan/Stud-Pres-ST.pdf

       Topics and Literature 

Centers, medians, centroids, diameters of trees and other graphs

  1. Goldman, A.J., Optimal center location in simple networks, Transportation Science, 5, 212-221 (1971)
  2. Tancel, B.C., Francis, R.L., Lowe, T.J.: Location on Networks, Parts 1,2. Management Science, 29, 482-511 (1983)
  3. Chepoi V.D. and Dragan F.F., Linear-time algorithm for finding a central vertex of a chordal graph, ''Algorithms - ESA'94 '' Second Annual European Symposium, Utrecht, The Netherlands, September 1994, Springer, LNCS 855 (Jan van Leeuwen, ed.), 159-170, 1994.
  4. V.D. Chepoi, F.F. Dragan, B. Estellon, M. Habib and Y. Vaxes, Diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs, Proceedings of the 24th Annual ACM Symposium on Computational Geometry (SoCG 2008), June 9–11, 2008, College Park, Maryland, USA, pp. 59-68.

 

p-Centers, r-domination,  p-medians of trees and other graphs

 

  1. O. Kariv and S. L. Hakimi: An Algorithmic Approach to Network Location Problems. I: The p-Centers, SIAM J. Appl. Math., Volume 37, Issue 3, pp. 513-538 (1979)
  2. O. Kariv and S. L. Hakimi: An Algorithmic Approach to Network Location Problems. II: The p-Medians, SIAM J. Appl. Math., Volume 37, Issue 3, pp. 539-560 (1979)
  3. J. Plesnik: A heuristic for the p-center problem in graphs, Discrete Applied Mathematics, Volume 17, Issue 3,  Pages: 263 - 268  (1987)
  4. Brandstädt, Chepoi V.D. and Dragan F.F.: The algorithmic use of hypertree structure and maximum neighbourhood orderings, Discrete Appl. Math.,  82 (1998), 43-77.
  5. Book: D. Hochbaum (ed.) “Approximation Algorithms for NP-hard Problems” PWS Publ.Co. 1995

 

Self-stabilizing algorithms for centers and medians of trees

 

10.     G. Antonoiu and P. K. Srimani, A Self-Stabilizing Distributed Algorithm to Find the Median of a Tree Graph, Journal of Computer and System Sciences, Volume 58, Issue 1, February 1999, Pages 215-221.

11.     S. C. Bruell, S. Ghosh, M. H. Karaata, and S. V. Pemmaraju, Self-Stabilizing Algorithms for Finding Centers and Medians of Trees, SIAM J. Comput., Volume 29, Issue 2, pp. 600-614 (1999)

12.     S. M. Hedetniemi, S. T. Hedetniemi, D. P. Jacobs and P. K. Srimani, Self-stabilizing algorithms for minimal dominating sets and maximal independent sets. Computers & Mathematics with Applications, Volume 46, Issues 5-6, September 2003, Pages 805-811.

Labeling schemes: NCA-queries, adjacency, ancestry

13.    S. Kannan, M. Naor, S. Rudich, Implicit representation of graphs, Proceedings of the twentieth annual ACM symposium on Theory of Computing,  Pages: 334 - 343  (1988).

14.     Book: J. Spinrad, Efficient Graph Representations, Fields Institute Monographs, 19, 2003.

15.     N. Santoro and R. Khatib, Labelling and Implicit Routing in Networks,  The Computer Journal,  28(1):5-8 (1985)

16.     Serge Abiteboul, Haim Kaplan, Tova Milo, Compact labeling schemes for ancestor queries, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms,  Pages: 547 - 556, 2001

17.     Haim Kaplan, Tova Milo, Ronen Shabo, A comparison of labeling schemes for ancestor queries, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms,  Pages: 954 - 963, 2002   

18.     Stephen Alstrup, Cyril Gavoille, Haim Kaplan, Theis Rauhe: Nearest common ancestors: a survey and a new distributed algorithm,  Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures,  Pages: 258 - 264, 2002;  also:  http://www.it-c.dk/people/stephen/Papers/ITU-TR-2001-6.ps

Labeling schemes: connectivity, reachability, distance

19.    Book: D. Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM Monographs on Discrete Mathematics and Applications, 2000.

20.     David Peleg: Proximity-Preserving Labeling Schemes and Their Applications. WG 1999: 30-41

21.     David Peleg: Informative labeling schemes for graphs. Theor. Comput. Sci. 340(3): 577-593 (2005)

22.     V.D. Chepoi, F.F. Dragan, Y. Vaxès, Addressing, distances and routing in triangular systems with applications in cellular networks,
Wireless Networks 12 (2006), 671-679.

23.     Cyril Gavoille, David Peleg, Stéphane Pérennes, Ran Raz: Distance labeling in graphs. J. Algorithms 53(1): 85-112 (2004)

24.     Cyril Gavoille, Michal Katz, Nir A. Katz, Christophe Paul, David Peleg: Approximate Distance Labeling Schemes. ESA 2001: 476-487.

25.     Slivkins, Distance estimation and object location via rings of neighbors, PODC 2005, pp. 41--50.

26.     Mikkel Thorup, Uri Zwick: Approximate distance oracles. STOC 2001: 183-192

27.     Michal Katz, Nir A. Katz, Amos Korman, David Peleg: Labeling Schemes for Flow and Connectivity. SIAM J. Comput. 34(1): 23-40 (2004)

28.     Mikkel Thorup: Compact Oracles for Reachability and Approximate Distances in Planar Digraphs. FOCS 2001: 242-251

29.     Amos Korman, David Peleg: Compact separator decompositions in dynamic trees and applications to labeling schemes. Distributed Computing 21(2): 141-161 (2008)

Network design: minimum spanning trees, diameter-bounded minimum spanning trees, light approximate shortest path trees, Steiner trees, optimal communication spanning trees

30.    Book: B.Y. Wu and K.-M. Chao “Spanning Trees and Optimization Problems”, CRC Press, 2003

31.     Book: J. Cheriyan and R. Ravi,  Approximation Algorithms for Networks Problems, http://www.gsia.cmu.edu/afs/andrew/gsia/ravi/WWW/new-lecnotes.html

32.     David Peleg, Eilon Reshef: Deterministic Polylog Approximation for Minimum Communication Spanning Trees. ICALP 1998: 670-681.

33.     David Peleg: Low Stretch Spanning Trees. MFCS 2002: 68-80.

34.     Noga Alon, Richard M. Karp, David Peleg, Douglas B. West: A Graph-Theoretic Game and Its Application to the k-Server Problem. SIAM J. Comput. 24(1): 78-100 (1995)

Graph Spanners

  1. Book: D. Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM Monographs on Discrete Mathematics and Applications, 2000. (the same as 19)
  2. D. Peleg, A.A. Schaffer, Graph spanners, Journal of Graph Theory 13 (1) (1989) 99–116.
  3. V.D. Chepoi, Dragan F.F., and Chenyu Yan, Additive Sparse Spanners for Graphs with Bounded Length of Largest Induced Cycle Theoretical Computer Science 347 (2005), 54-75.
  4. Y. Dourisboure, Dragan F.F., C. Gavoille, and C. Yan, Spanners for bounded tree-length spanners, Theoretical. Computer Science 383 (2007),  34-44.
  5. Victor Chepoi, Feodor F. Dragan, Bertrand Estellon, Michel Habib, Yann Vaxes and Yang Xiang, Additive Spanners and Distance and Routing Labeling Schemes for delta-Hyperbolic Graphs, manuscript 2008.
  6. M. Elkin, D. Peleg, (1 + epsilon, beta)-spanner constructions for general graphs, 33rd Annual ACM Symposium on Theory of Computing, STOC, Hersonissos, Crete, Greece, 2001, pp. 173–182.
  7. S. Baswana, T. Kavitha, K. Mehlhorn, S. Pettie, New constructions of (alpha, beta)-spanners and purely additive spanners, 16th Symposium on Discrete Algorithms, SODA, ACM–SIAM, 2005, pp. 672–681.
  8. Althofer, G. Das, D. Dobkin, D. Joseph, J. Soares, On sparse spanners of weighted graphs, Discrete & Computational Geometry 9 (1) (1993) 81–100.
  9. M. Thorup, U. Zwick, Approximate distance oracles, 33rd Annual ACM Symposium on Theory of Computing, STOC, Hersonissos, Crete, Greece, 2001, pp. 183–192. (the same as 26)
  10. S. Baswana, S. Sen, A simple linear time algorithm for computing a (2k − 1)-spanner of O(n1+1/k ) size in weighted graphs, 30th International Colloquium on Automata, Languages and Programming, ICALP, in: Lecture Notes in Computer Science, vol. 2719, Springer, 2003, pp. 384–396.
  11. Bilel Derbel, Cyril Gavoille, David Peleg, Laurent Viennot: On the locality of distributed sparse spanner construction. PODC 2008: 273-282.
  12. Li, X.-Y., Wang, Y.:  Geometrical Spanner for Wireless Ad Hoc Networks. Handbook of Approximation Algorithms and Metaheuristics (Editor: Teofilo F. Gonzalez), Chapman & Hall/Crc (2006)
  13. Gao, J., Guibas, L.J., Hershberger, J., Zhang, L., Zhu, A.: Geometric spanner for routing in mobile networks. Proceedings of the 2nd ACM international symposium on mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA
  14. F.F. Dragan, F. Fomin and P. Golovach, A PTAS for the sparsest spanners problem on apex-minor-free graphs, 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008), Torun, Poland, August 27-31, 2008, Springer, Lecture Notes in Computer Science 5162, pp. 290-298.
  15. F.F. Dragan, F. Fomin and P. Golovach, Spanners in sparse graphs, 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), Reykjavik, Iceland,  July 6-13, 2008, Springer, Lecture Notes in Computer Science 5125 (Part I), pp. 597-608.

Tree spanners, collective tree spanners, flow spanners

  1. L. Cai, D.G. Corneil, Tree spanners, SIAM Journal on Discrete Mathematics 8 (3) (1995) 359–387.
  2. Brandstädt, Dragan F.F., H.-O. Le, and V.B. Le, Tree Spanners on Chordal Graphs: Complexity and Algorithms, Theoretical Computer Science  310 (2004), 329-354.
  3. Brandstädt, Dragan F.F., H.-O. Le, V.B. Le and R. Uehara, Tree spanners for bipartite graphs and probe interval graphs, Algorithmica 47 (2007), 27–51.
  4. Stefan Eckhardt and Sebastian Wernicke, On the Algorithmic Intractability of Computing Distance-Approximating Spanning Trees, Preprint: http://wwwbib.informatik.tu-muenchen.de/infberichte/2004/TUM-I0409.pdf.gz
  5. Yuval Emek, David Peleg: Approximating Minimum Max-Stretch spanning Trees on unweighted graphs. SODA 2004: 261-270.
  6. Christian Liebchena and Gregor Wünsch, The zoo of tree spanner problems, Discrete Applied Mathematics, Volume 156, Issue 5, 1 March 2008, Pages 569-587.
  7. F.F. Dragan, C. Yan and  I. Lomonosov, Collective tree spanners of graphs, SIAM J. Discrete Math. 20 (2006),  241-260.
  8. F.F. Dragan, C. Yan and D.G. Corneil, Collective Tree Spanners and Routing in AT-free Related Graphs, Journal of Graph Algorithms and Applications, Vol. 10, no. 2, 2006, 97-122.
  9. F.F. Dragan and C. Yan, Network Flow Spanners, Proceedings of the 7th Latin American Symposium ''LATIN 2006: Theoretical Informatics'', Valdivia, Chile, March 20-24, Springer, Lecture Notes in Computer Science 3887, pp. 410-422.

Navigating in a graph: Message routing, hierarchical cluster-based routing, interval routing, labeling routing schemes, routing in mobile ad-hoc networks, pseudo coordinates, navigating with aid.

  1. C. Gavoille, A survey on interval routing schemes, Theoretical Computer Science, 245 (1999), 217--253.
  2. Thorup, M., Zwick, U.: Compact routing schemes. In: Proceedings of the 13th Ann. ACM Symp. on Par. Alg. and Arch. (SPAA 2001), pp. 1–10.
  3. Y. Dourisboure, Compact Routing Schemes for Bounded Tree-Length Graphs and for k-Chordal Graphs, DISC 2004, 365--378.
  4. Victor Chepoi, Feodor F. Dragan, Bertrand Estellon, Michel Habib, Yann Vaxes and Yang Xiang, Additive Spanners and Distance and Routing Labeling Schemes for delta-Hyperbolic Graphs, manuscript 2008. (the same as 36)
  5. Abraham, C. Gavoille, A.V. Goldberg, D. Malkhi, Routing in Networks with Low Doubling Dimension, ICDCS 2006, p. 75 (see also  http://dept-info.labri.fr/~gavoille/article/AGGM06).
  6. H. T.-H. Chan, A. Gupta, B. M. Maggs, and S. Zhou, On hierarchical routing in doubling metrics, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, British Columbia, Canada, January 23-25, 2005. SIAM, pp. 762--771.
  7. Slivkins, Distributed approaches to triangulation and embedding, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, British Columbia, Canada, January 23-25, 2005, SIAM, pp. 640-649.
  8. Slivkins, Distance estimation and object location via rings of neighbors, PODC 2005, pp. 41--50. (the same as 25)
  9. K. Talwar, Bypassing the embedding: Algorithms for low dimensional metrics, STOC 2004, pp.  281--290.
  10. S. Giordano and I. Stojmenovic, Position based routing algorithms for ad hoc networks: A taxonomy, In X. Cheng, X. Huang, and D. Du, editors, Ad Hoc Wireless Networking, pages 103-136. Kluwer, 2004.
  11. Karp and H.T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th ACM/IEEE MobiCom., 2000, ACM Press, pp. 243-254.
  12. J.M. Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC 2000), May 21-23, 2000, Portland, OR, USA. ACM, pp. 163-170.
  13. Rao, C. Papadimitriou, S. Shenker, and I. Stoica, Geographical routing without location information, Proceedings of MobiCom 2003, 2003, pp. 96--108.
  14. R. Kleinberg, Geographic routing using hyperbolic space,   In  INFOCOM 2007, pp. 1902-1909.
  15. F.F. Dragan and M. Matamala, Navigating in a graph by aid of its spanning tree, 19th International Symposium on Algorithms and Computation (ISAAC 2008), Surfers Paradise, Gold Coast, Australia, December 15-17, 2008, Springer, Lecture Notes in Computer Science 5369, pp. 789–800, 2008.

Balanced separators of graphs and their algorithmic use

  1. Nathan Linial, Eran London, Yuri Rabinovich: The Geometry of Graphs and Some of its Algorithmic Applications. Combinatorica 15(2): 215-245 (1995)
  2. F.F. Dragan and C. Yan, Collective Tree Spanners in Graphs with Bounded Genus, Chordality, Tree-width, or Clique-width, In Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005), December 19-21, 2005, Hainan, China, Springer, Lecture Notes in Computer Science 3827, pp. 583–592.
  3. Gupta, A., Kumar, A., Rastogi, R.: Traveling with a Pez Dispenser (Or, Routing Issues in MPLS). SIAM J. Comput., 34 (2005), pp. 453–474.
  4. V.D. Chepoi, F.F. Dragan, Y. Vaxès, Distance and routing labeling schemes for non-positively curved plane graphs, Journal of Algorithms 61 (2006), 60-88.
  5. F.F. Dragan, D.G. Corneil, E. Köhler and Y. Xiang, Additive Spanners for Circle Graphs and Polygonal Graphs, 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2008),  Durham University, U.K., June 30- July 2, 2008, Springer, Lecture Notes in Computer Science  5344, pp. 110–121, 2008.
  6. Abraham, C. Gavoille, Object location using path separators, Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing (PODC 2006)}, Denver, Colorado, USA, July 23-26, 2006, ACM, pp  188-197.
  7. Chenyu Yan, Yang Xiang and Feodor F. Dragan, Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs, manuscript 2008.
  8. See also 20, 21, 23, 28.

 

 F. F. Dragan
dragan at cs kent edu
Spring 2009