Graphs & Applications
Publications of Ralf KLASING
(bibtex format)
Copyrights for some of the papers below have been
transfered, or will be transfered to various publishers of journals,
conferences proceedings, etc. For such papers I am required to post the
following notice: This material is presented to ensure timely dissemination
of scholarly and technical work. Copyright and all rights therein are
retained by authors or by other copyright holders. All persons copying
this information are expected to adhere to the terms and constraints
invoked by each author's copyright. Publisher's copyright policy
are available at
© SIAM,
© ACM,
© IEEE,
© Springer,
© Elsevier,
© Ideal,
© King's College.
[
2008 |
2007 |
2006 |
2005 |
2004 |
2003 |
2002 |
2000 |
1999 |
1998 |
1997 |
1996 |
1995 |
1994 |
1993 |
1992 |
1991 |
1990]
2008
- Ralf Klasing, Nelson Morales, and Stéphane Pérennes. On the complexity of bandwidth allocation in radio networks. Theoretical Computer Science, 2008. to appear.
- Ralf Klasing, Euripides Markou, Tomasz Radzik, and Fabiano Sarracco. Approximation bounds for black hole search problems. Networks, 2008. to appear.
- Ralf Klasing, Euripides Markou, and Andrzej Pelc. Gathering asynchronous oblivious mobile robots in a ring. Theoretical Computer Science, 2008. to appear.
- Subir Bandyopadhyay (in cooperation with Ralf Klasing). Dissemination of Information in Optical Networks: From Technology to Algorithms. Springer Monograph. Springer-Verlag, 2008.
- Sylvain Gravier, Ralf Klasing, and Julien Moncel. Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs. Algorithmic Operations Research, 2008. to appear.
- Leszek Gasieniec, Ralf Klasing, Russell Martin, Alfredo Navarra, and Xiaohui Zhang. Fast periodic graph exploration with constant memory. Journal of Computer and System Sciences, 2008. to appear.
- Michele Flammini, Ralf Klasing, Alfredo Navarra, and Stéphane Pérennes. Tightening the upper bound for the minimum energy broadcasting. Wireless Networks, 2008. Online First.
- Colin Cooper, Ralf Klasing, and Tomasz Radzik. A randomized algorithm for the joining protocol in dynamic distributed networks. Theoretical Computer Science, 2008. to appear.
2007
- Cyril Gavoille, Ralf Klasing, Adrian Kosowski, Lukasz Kuszner, and Alfredo Navarra. On the complexity of distributed graph coloring with local minimality constraints. Technical Report RR-1440-07, LaBRI, December 2007. appears also as INRIA Research Report RR-6399, December 2007.
- Michele Flammini, Ralf Klasing, Alfredo Navarra, and Stéphane Pérennes. Improved approximation results for the minimum energy broadcasting problem in wireless ad hoc networks. Algorithmica, 49(4):318-336, December 2007.
- Ralf Klasing, Euripides Markou, Tomasz Radzik, and Fabiano Sarracco. Hardness and approximation results for black hole search in arbitrary graphs. Theoretical Computer Science, 384(2-3):201-221, October 2007.
- Ralf Klasing, Zvi Lotker, Alfredo Navarra, and Stéphane Pérennes. From balls and bins to points and vertices. Technical Report RR-1437-07, LaBRI, October 2007.
- Ralf Klasing, Adrian Kosowski, and Alfredo Navarra. Cost minimisation in wireless networks with a bounded and unbounded number of interfaces. Technical Report RR-1436-07, LaBRI, September 2007.
- Cyril Gavoille, Ralf Klasing, Adrian Kosowski, and Alfredo Navarra. On the complexity of distributed greedy coloring. In Proceedings of the 21st International Symposium on Distributed Computing (DISC 2007), volume 4731 of Lecture Notes in Computer Science, pages 482-484. Springer Verlag, September 2007.
- Ralf Klasing, Adrian Kosowski, and Alfredo Navarra. Cost minimisation in multi-interface networks. In Proceedings of the 1st Annual International Conference on Network Control and Optimization (NET-COOP 2007), volume 4465 of Lecture Notes in Computer Science, pages 276-285. Springer Verlag, June 2007.
- Leszek Gasieniec, Ralf Klasing, Russell Martin, Alfredo Navarra, and Xiaohui Zhang. Fast periodic graph exploration with constant memory. In Proceedings of the 14th Colloquium on Structural Information and Communication Complexity (SIROCCO 2007), volume 4474 of Lecture Notes in Computer Science, pages 26-40. Springer Verlag, June 2007.
- Colin Cooper, Ralf Klasing, and Tomasz Radzik. A randomized algorithm for the joining protocol in dynamic distributed networks. Technical Report RR-1432-07, LaBRI, June 2007.
- Hans-Joachim Böckenhauer, Dirk Bongartz, Juraj Hromkovic, Ralf Klasing, Guido Proietti, Sebastian Seibert, and Walter Unger. On k-connectivity problems with sharpened triangle inequality. Technical Report RR-1430-07, LaBRI, May 2007.
- Leszek Gasieniec, Ralf Klasing, Russell Martin, Alfredo Navarra, and Xiaohui Zhang. Fast periodic graph exploration with constant memory. Technical Report RR-1426-07, LaBRI, April 2007.
- Ralf Klasing, Euripides Markou, and Andrzej Pelc. Gathering asynchronous oblivious mobile robots in a ring. Technical Report RR-1422-07, LaBRI, January 2007.
2006
- Ralf Klasing, Euripides Markou, and Andrzej Pelc. Gathering asynchronous oblivious mobile robots in a ring. In Proceedings of the 17th Annual International Symposium on Algorithms and Computation (ISAAC 2006), volume 4288 of Lecture Notes in Computer Science, pages 744-753. Springer Verlag, December 2006.
- Colin Cooper, Ralf Klasing, and Tomasz Radzik. Searching for black-hole faults in a network using multiple agents. In Proceedings of the 10th International Conference on Principles of Distributed Systems (OPODIS 2006), volume 4305 of Lecture Notes in Computer Science, pages 320-332. Springer Verlag, December 2006.
- Sylvain Gravier, Ralf Klasing, and Julien Moncel. Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs. Technical Report RR-1417-06, LaBRI, November 2006.
- Juraj Hromkovic, Przemyslawa Kanarek, Ralf Klasing, Krzysztof Lorys, Walter Unger, and Hubert Wagener. On the size of permutation networks and consequences for efficient simulation of hypercube algorithms on bounded-degree networks. Technical Report RR-1410-06, LaBRI, September 2006.
- Ralf Klasing, Euripides Markou, Tomasz Radzik, and Fabiano Sarracco. Approximation bounds for black hole search problems. Technical Report RR-1407-06, LaBRI, July 2006. appears also as INRIA Research Report RR-6185, May 2007.
- Jean-Claude Bermond, Jérôme Galtier, Ralf Klasing, Nelson Morales, and Stéphane Pérennes. Hardness and approximation of gathering in static radio networks. Technical report, INRIA Research Report RR-5936 and LaBRI Research Report RR-1403-06, June 2006.
- Jean-Claude Bermond, Jérôme Galtier, Ralf Klasing, Nelson Morales, and Stéphane P& acute;erennes. Hardness and approximation of gathering in static radio networks. Parallel Processing Letters, 16(2):165-183, June 2006.
- Jean-Claude Bermond, Jérôme Galtier, Ralf Klasing, Nelson Morales, and Stéphane P& acute;erennes. Gathering in specific radio networks. In 8èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel06), Trégastel, pages 85-88, May 2006.
- Jean-Claude Bermond, Jérôme Galtier, Ralf Klasing, Nelson Morales, and Stéphane Pérennes. Hardness and approximation of gathering in static radio networks. In FAWN06, Pisa, Italy, pages 75-79, March 2006.
- Ralf Klasing, Euripides Markou, Tomasz Radzik, and Fabiano Sarracco. Approximation bounds for black hole search problems. In Proceedings of the 9th International Conference on Principles of Distributed Systems (OPODIS 2005), volume 3974 of Lecture Notes in Computer Science, pages 261-274. Springer Verlag, 2006.
- Ralf Klasing, Christian Laforest, Joseph G. Peters, and Nicolas Thibault. Constructing incremental sequences in graphs. Algorithmic Operations Research, 1(2):1-7, 2006.
2005
- Ralf Klasing, Zvi Lotker, Alfredo Navarra, and Stéphane Pérennes. From balls and bins to points and vertices. In Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005), volume 3827 of Lecture Notes in Computer Science, pages 757-766. Springer Verlag, December 2005.
- Ralf Klasing, Euripides Markou, Tomasz Radzik, and Fabiano Sarracco. Hardness and approximation results for black hole search in arbitrary graphs. In Proceedings of the 12th Colloquium on Structural Information and Communication Complexity (SIROCCO 2005), volume 3499 of Lecture Notes in Computer Science, pages 200-215. Springer Verlag, May 2005.
- R. Klasing, E. Markou, T. Radzik, and F. Sarracco. Approximation results for black hole search in arbitrary networks. Research report, INRIA Research Report RR-5659 and I3S Research Report I3S/RR-2005-23-FR, 2005.
- R. Klasing, C. Laforest, J. Peters, and N. Thibault. Constructing incremental sequences in graphs. Research report, INRIA Research Report RR-5648 and I3S Research Report I3S/RR-2005-22-FR, 2005.
- J. Hromkovic, R. Klasing, A. Pelc, P. Ruzicka, and W. Unger. Dissemination of Information in Communication Networks: Part I. Broadcasting, Gossiping, Leader Election, and Fault-Tolerance. Springer Monograph. Springer-Verlag, 2005.
- Colin Cooper, Ralf Klasing, and Michele Zito. Lower bounds and algorithms for dominating sets in web graphs. Internet Mathematics, 2(3):275-300, 2005.
- C. Cooper, R. Klasing, and M. Zito. Lower bounds and algorithms for dominating sets in web graphs. Technical report, INRIA Research Report RR-5529 and I3S Research Report I3S/RR-2005-09-FR, 2005.
2004
- H.-J. Böckenhauer, D. Bongartz, J. Hromkovic, R. Klasing, G. Proietti, S. Seibert, and W. Unger. On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality. Theoretical Computer Science, 326(1-3):137-153, October 2004.
- M. Flammini, R. Klasing, A. Navarra, and S. Pérennes. Improved approximation results for the minimum energy broadcasting problem. In Workshop on Discrete Algorithms and Methods for MOBILE Computing and Communications, Proceedings of the 2004 joint workshop on Foundations of mobile computing, pages 85-91. ACM Press, October 2004.
- C. Cooper, R. Klasing, and M. Zito. Dominating sets in web graphs. In Algorithms and Models for the Web-Graph: Third International Workshop, WAW 2004, volume 3243 of Lecture Notes in Computer Science, pages 31-43. Springer-Verlag, October 2004.
- R. Klasing, A. Navarra, A. Papadopoulos, and S. Pérennes. Adaptive broadcast consumption (abc), a new heuristic and new bounds for the minimum energy broadcast routing problem. In NETWORKING 2004, Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communications: Third International IFIP-TC6 Networking Conference, volume 3042 of Lecture Notes in Computer Science, pages 866-877. Springer-Verlag, May 2004.
- R. Klasing, N. Morales, and S. Pérennes. Complexity of bandwidth allocation in radio networks: the static case. Research report, INRIA Research Report RR-5432 and I3S Research Report I3S/RR-2004-40-FR, 2004.
- R. Klasing, Z. Lotker, A. Navarra, and S. Pérennes. The points and vertices game. Technical Report TRCS 030/2004, Dipartimento di Informatica, Università degli Studi di L'Aquila, 2004.
- R. Klasing and C. Laforest. Hardness results and approximation algorithms of k-tuple domination in graphs. Information Processing Letters, 89(2):75-83, January 2004.
- C. Cooper, R. Klasing, and T. Radzik. A randomized algorithm for the joining protocol in dynamic distributed networks. Research report, INRIA Research Report RR-5376 and I3S Research Report I3S/RR-2004-39-FR, 2004.
2003
- H.-J. Böckenhauer, D. Bongartz, J. Hromkovic, R. Klasing, G. Proietti, S. Seibert, and W. Unger. On k-edge-connectivity problems with sharpened triangle inequality (extended abstract). In Algorithms and Complexity: 5th Italian Conference, CIAC 2003, volume 2653 of Lecture Notes in Computer Science, pages 189-200. Springer-Verlag, May 2003.
2002
- H.-J. Böckenhauer, D. Bongartz, J. Hromkovic, R. Klasing, G. Proietti, S. Seibert, and W. Unger. On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality (extended abstract). In FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science: 22nd Conference, volume 2556 of Lecture Notes in Computer Science, pages 59-70. Springer-Verlag, December 2002.
- H.-J. Böckenhauer, J. Hromkovic, R. Klasing, S. Seibert, and W. Unger. Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. Theoretical Computer Science, 285(1):3-24, August 2002.
2000
- H.-J. Böckenhauer, J. Hromkovic, R. Klasing, S. Seibert, and W. Unger. Approximation algorithms for the tsp with sharpened triangle inequality. Information Processing Letters, 75(3):133-138, August 2000.
- H.-J. Böckenhauer, J. Hromkovic, R. Klasing, S. Seibert, and W. Unger. Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. In Algorithms and Complexity: 4th Italian Conference, CIAC 2000, volume 1767 of Lecture Notes in Computer Science, pages 72-86. Springer-Verlag, March 2000.
- H.-J. Böckenhauer, J. Hromkovic, R. Klasing, S. Seibert, and W. Unger. An improved lower bound on the approximability of metric tsp and approximation algorithms for the tsp with sharpened triangle inequality. In STACS 2000: 17th Annual Symposium on Theoretical Aspects of Computer Science, volume 1770 of Lecture Notes in Computer Science, pages 382-394. Springer-Verlag, February 2000.
1999
- H.-J. Böckenhauer, J. Hromkovic, R. Klasing, S. Seibert, and W. Unger. Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. Research Report TR99-031, Electronic Colloquium on Computational Complexity (ECCC), September 1999.
1998
- R. Klasing, R. Lüling, and B. Monien. Compressing cube-connected cycles and butterfly networks. Networks, 32(1):47-65, December 1998.
- R. Klasing. Improved compressions of cube-connected cycles networks. IEEE Transactions on Parallel and Distributed Systems, 9(8):803-812, August 1998.
- R. Klasing. Improved compressions of cube-connected cycles networks. In 24rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG '98), volume 1517 of Lecture Notes in Computer Science, pages 242-256. Springer-Verlag, June 1998.
- J. Hromkovic, R. Klasing, D. Pardubská, J. Waczulík, and H. Wagener. Effective systolic algorithms for gossiping in cycles. Parallel Processing Letters, 8(2):197-205, June 1998.
- R. Klasing. The relationship between the gossip complexity in vertex-disjoint paths mode and the vertex bisection width. Discrete Applied Mathematics, 83(1-3):229-246, March 1998.
- R. Heckmann, R. Klasing, B. Monien, and W. Unger. Optimal embedding of complete binary trees into lines and grids. Journal of Parallel and Distributed Computing, 49(1):40-56, February 1998.
1997
- J. Hromkovic, R. Klasing, W. Unger, and H. Wagener. Optimal algorithms for broadcast and gossip in the edge-disjoint path modes. Information and Computation, 133(1):1-33, February 1997.
1996
- J. Hromkovic, R. Klasing, and E.A. Stöhr. Dissemination of information in vertex-disjoint paths mode. Computers and Artificial Intelligence, 15(4):295-318, 1996.
- J. Hromkovic, R. Klasing, B. Monien, and R. Peine. Combinatorial Network Theory, chapter Dissemination of Information in Interconnection Networks (Broadcasting and Gossiping), pages 125-212. Kluwer Academic Publishers, 1996.
1995
- J. Hromkovic, R. Klasing, E. Stöhr, and H. Wagener. Gossiping in vertex-disjoint paths mode in d-dimensional grids and planar graphs. Information and Computation, 123(1):17-28, November 1995.
- J. Hromkovic, R. Klasing, D. Pardubská, W. Unger, J. Waczulík, and H. Wagener. Effective systolic algorithms for gossiping in cycles and two-dimensional grids (extended abstract). In H. Reichel, editor, Fundamentals of Computation Theory, 10th International Symposium, FCT '95, volume 965 of Lecture Notes in Computer Science, pages 273-282. Springer, August 1995.
- J. Hromkovic, K. Lorys, P. Kanarek, R. Klasing, W. Unger, and H. Wagener. On the sizes of permutation networks and consequences for efficient simulation of hypercube algorithms on bounded-degree networks. In E. W. Mayr and C. Puech, editors, STACS 95, 12th Annual Symposium on Theoretical Aspects of Computer Science, volume 900 of Lecture Notes in Computer Science, pages 255-266. Springer, March 1995.
- B. Monien, R. Diekmann, R. Feldmann, R. Klasing, R. Lüling, K. Menzel, T. Römke, and U.-P. Schroeder. Computer Science Today: Recent Trends and Developments, volume 1000 of Lecture Notes in Computer Science, chapter Efficient Use of Parallel & Distributed Systems: From Theory to Practice, pages 62-77. Springer, 1995.
1994
- R. Klasing, B. Monien, R. Peine, and E. Stöhr. Broadcasting in butterfly and debruijn networks. Discrete Applied Mathematics, 53(1-3):183-197, September 1994.
- R. Klasing. The relationship between gossiping in vertex-disjoint paths mode and bisection width. In I. Prívara, B. Rovan, and P. Ruzicka, editors, Mathematical Foundations of Computer Science 1994, 19th International Symposium, MFCS'94, volume 841 of Lecture Notes in Computer Science, pages 473-483. Springer, August 1994.
- J. Hromkovic, R. Klasing, W. Unger, and H. Wagener. Optimal algorithms for broadcast and gossip in the edge-disjoint path modes (extended abstract). In E. M. Schmidt and S. Skyum, editors, Algorithm Theory - SWAT '94, 4th Scandinavian Workshop on Algorithm Theory, volume 824 of Lecture Notes in Computer Science, pages 219-230. Springer, July 1994.
- J. Hromkovic, R. Klasing, W. Unger, H. Wagener, and D. Pardubská. The complexity of systolic dissemination of information in interconnection networks. In M. Cosnard, A. Ferreira, and J. G. Peters, editors, Parallel and Distributed Computing, First Canada-France Conference, volume 805 of Lecture Notes in Computer Science, pages 235-249. Springer, May 1994.
- J. Hromkovic, R. Klasing, W. Unger, H. Wagener, and D. Pardubská. The complexity of systolic dissemination of information in interconnection networks. R.A.I.R.O. Theoretical Informatics and Applications, 28(3-4):303-342, 1994.
1993
- J. Hromkovic, R. Klasing, E. Stöhr, and H. Wagener. Gossiping in vertex-disjoint paths mode in d-dimensional grids and planar graphs. In T. Lengauer, editor, Algorithms - ESA '93, First Annual European Symposium, volume 726 of Lecture Notes in Computer Science, pages 200-211. Springer, October 1993.
- J. Hromkovic, R. Klasing, and E. Stöhr. Gossiping in vertex-disjoint path mode in interconnection networks. In J. van Leeuwen, editor, Graph-Theoretic Concepts in Computer Science, 19th International Workshop, WG '93, volume 790 of Lecture Notes in Computer Science, pages 288-300. Springer, June 1993.
- B. Monien, R. Feldmann, R. Klasing, and R. Lüling. Parallel architectures: Design and efficient use. In P. Enjalbert, A. Finkel, and K. W. Wagner, editors, STACS 93, 10th Annual Symposium on Theoretical Aspects of Computer Science, volume 665 of Lecture Notes in Computer Science, pages 247-269. Springer, February 1993.
1992
- R. Klasing, B. Monien, R. Peine, and E. Stöhr. Broadcasting in butterfly and debruijn networks. In A. Finkel and M. Jantzen, editors, STACS 92, 9th Annual Symposium on Theoretical Aspects of Computer Science, volume 577 of Lecture Notes in Computer Science, pages 351-362. Springer, February 1992.
1991
- R. Heckmann, R. Klasing, B. Monien, and W. Unger. Optimal embedding of complete binary trees into lines and grids. In G. Schmidt and R. Berghammer, editors, 17th International Workshop, WG '91, volume 570 of Lecture Notes in Computer Science, pages 25-35. Springer, June 1991.
1990
- R. Klasing, R. Lüling, and B. Monien. Compressing cube-connected cycles and butterfly networks. In 2nd IEEE Symposium on Parallel and Distributed Processing, SPDP '90, pages 858-865, December 1990.
22 janvier 2008 (77)
[home page of the team]