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

(Research oriented Course)

Spring 2013

TR :30 pm - 6:45 pm, MSB 104

Instructor
Office Hours   
   
      
Email 
Telephone

Dr. Feodor Dragan 
Room 254 MSB
TR 3:00 - 5:00 pm
and by appointment 
dragan at cs kent edu
(330)  672-9058

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

5.       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)

6.       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)

7.       J. Plesnik: A heuristic for the p-center problem in graphs, Discrete Applied Mathematics, Volume 17, Issue 3,  Pages: 263 - 268  (1987)

8.       Brandstaedt, Chepoi V.D. and Dragan F.F.: The algorithmic use of hypertree structure and maximum neighbourhood orderings, Discrete Appl. Math.,  82 (1998), 43-77.

9.       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. Vaxes, Addressing, distances and routing in triangular systems with applications in cellular networks,
Wireless Networks 12 (2006), 671-679.

23.    Cyril Gavoille, David Peleg, Stephane Perennes, 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

35.    Book: D. Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM Monographs on Discrete Mathematics and Applications, 2000. (the same as 19)

36.    D. Peleg, A.A. Schaffer, Graph spanners, Journal of Graph Theory 13 (1) (1989) 99-116.

37.    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.

38.    Y. Dourisboure, Dragan F.F., C. Gavoille, and C. Yan, Spanners for bounded tree-length spanners, Theoretical. Computer Science 383 (2007), 34-44.

39.    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, Algorithmica 62 (2012), 713-732.

40.    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.

41.    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.

42.    Althofer, G. Das, D. Dobkin, D. Joseph, J. Soares, On sparse spanners of weighted graphs, Discrete & Computational Geometry 9 (1) (1993) 81-100.

43.    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)

44.    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.

45.    Bilel Derbel, Cyril Gavoille, David Peleg, Laurent Viennot: On the locality of distributed sparse spanner construction. PODC 2008: 273-282.

46.    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)

47.    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

48.    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.

49.    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

50.    L. Cai, D.G. Corneil, Tree spanners, SIAM Journal on Discrete Mathematics 8 (3) (1995) 359-387.

51.    Brandstaedt, 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.

52.    Brandstaedt, 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.

53.    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

54.    Yuval Emek, David Peleg: Approximating Minimum Max-Stretch spanning Trees on unweighted graphs. SODA 2004: 261-270.

55.    F.F. Dragan, E. Koehler, An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs,
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - Proceedings of the 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011, Lecture Notes in Computer Science 6845, Springer, pp. 171-183 (available on-line at DOI: 10.1007/978-3-642-22935-0_15)

56.    Christian Liebchena and Gregor Wuensch, The zoo of tree spanner problems, Discrete Applied Mathematics, Volume 156, Issue 5, 1 March 2008, Pages 569-587.

57.    F.F. Dragan, C. Yan and  I. Lomonosov, Collective tree spanners of graphs, SIAM J. Discrete Math. 20 (2006),  241-260.

58.    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.

59.    F.F. Dragan and M. Abu-Ata, Collective Additive Tree Spanners of Bounded Tree-Breadth Graphs with Generalizations and Consequences, CoRR abs/1207.2506: (2012)

60.    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.

 

Embeddings of graph metrics into metrics of simple graphs

61.    Nathan Linial, Eran London, Yuri Rabinovich: The Geometry of Graphs and Some of its Algorithmic Applications. Combinatorica 15(2): 215-245 (1995)

62.    V.D. Chepoi, F.F. Dragan, I. Newman, Y. Rabinovich and Y. Vaxes, Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs, Discrete & Computational Geometry 47(1): 187-214 (2012) (available on-line at DOI: 10.1007/s00454-011-9386-0)

63.    R. Agarwala, V. Bafna, M. Farach, B. Narayanan, M. Paterson, M. Thorup, On the approximability of numerical taxonomy (fitting distances by tree metrics), SIAM J. Comput. (28) (1999), 1073--1085.

64.    M. Badoiu, J. Chuzhoy, P. Indyk, A. Sidiropoulos, Low-distortion embeddings of general metrics into the line, Proceedings of the 37th Annual ACM

65.    Symposium on Theory of Computing (STOC 2005), Baltimore, MD, USA, May 22-24, 2005, ACM, pp. 225--233.

66.    M. Badoiu, E.D. Demaine, M.T. Hajiaghayi, A. Sidiropoulos, and M. Zadimoghaddam, Ordinal embedding: approximation algorithms and dimensionality reduction, Proceedings of the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2008), Boston, MA, USA, August 25-27, 2008, Springer, Lecture Notes in Computer Science 5171, pp. 21--34.

67.    M. Badoiu, P. Indyk, and A. Sidiropoulos, Approximation algorithms for embedding general metrics into trees, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), New Orleans, Louisiana, USA, January 7-9, 2007, ACM/SIAM, pp. 512--521.

68.    A. Brandstaedt, V. Chepoi, and F. Dragan, Distance approximating trees for chordal and dually chordal graphs, J. Algorithms 30 (1999), 166--184.

69.    V. Chepoi and F. Dragan, A note on distance approximating trees in graphs, Europ. J. Combin. 21 (2000), 761--766.

70.    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, Algorithmica 62 (2012), 713-732. (the same as 39)

71.    I. Abraham, M. Balakrishnan, F. Kuhn, D. Malkhi, V. Ramasubramanian, K. Talwar, Reconstructing approximate tree metrics, PODC 2007, pp. 43--52.

 

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.

72.    C. Gavoille, A survey on interval routing schemes, Theoretical Computer Science, 245 (1999), 217--253.

73.    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.

74.    Y. Dourisboure, Compact Routing Schemes for Bounded Tree-Length Graphs and for k-Chordal Graphs, DISC 2004, 365--378.

75.    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, Algorithmica 62 (2012), 713-732. (the same as 39)

76.    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).

77.    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.

78.    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.

79.    Slivkins, Distance estimation and object location via rings of neighbors, PODC 2005, pp. 41--50. (the same as 25)

80.    K. Talwar, Bypassing the embedding: Algorithms for low dimensional metrics, STOC 2004, pp. 281--290.

81.    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.

82.    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.

83.    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.

84.    Rao, C. Papadimitriou, S. Shenker, and I. Stoica, Geographical routing without location information, Proceedings of MobiCom 2003, 2003, pp. 96--108.

85.    R. Kleinberg, Geographic routing using hyperbolic space, In INFOCOM 2007, pp. 1902-1909.

86.    F.F. Dragan and M. Matamala, Navigating in a graph by aid of its spanning tree, SIAM J. Discrete Math., 25(1): 306-332 (2011).

87.    F.F. Dragan and Y. Xiang, How to use spanning trees to navigate in graphs, 34th International Symposium on Mathematical Foundations of Computer Science (MFCS 2009), August 24-28, 2009, Novy Smokovec, High Tatras, Slovak Republic, Springer, Lecture Notes in Computer Science 5734, pp. 282-294.

 

Balanced separators of graphs and their algorithmic use

88.    F.F. Dragan and C. Yan, Collective Tree Spanners in Graphs with Bounded Parameters, 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. (also, Algorithmica 57 (2010), 22-43.)

89.    Gupta, A., Kumar, A., Rastogi, R.: Traveling with a Pez Dispenser (Or, Routing Issues in MPLS). SIAM J. Comput., 34 (2005), pp. 453-474.

90.    V.D. Chepoi, F.F. Dragan, Y. Vaxes, Distance and routing labeling schemes for non-positively curved plane graphs, Journal of Algorithms 61 (2006), 60-88.

91.    F.F. Dragan, D.G. Corneil, E. Koehler 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.

92.    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.

93.    Chenyu Yan, Yang Xiang and Feodor F. Dragan, Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs, Computational Geometry: Theory and Applications 45(7): 305-325 (2012)

94.    V.D. Chepoi, F.F. Dragan, Y. Vaxes, Distance-Based Location Update and Routing in Irregular Cellular Networks, In Proceedings of Sixth International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing and First ACIS International Workshop on Self-Assembling Wireless Networks (SNPD/SAWN'05), May 23-25, 2005, Towson University, Maryland, USA, IEEE Computer Society, 2005, pp. 380-387.

95.    See also 20, 21, 23, 28, etc.

 

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

 

NOTICE OF MY COPYRIGHT AND INTELLECTUAL PROPERTY RIGHTS. Any intellectual property displayed or distributed to students during this course (including but not limited to powerpoint presentations, notes, quizzes, examinations) by the professor remains the intellectual property of the professor. This means that the student may not distribute, publish or provide such intellectual property to any other person or entity for any reason, commercial or otherwise, without the express written permission of the professor.