Dr Ralf Klasing - Publications
- Dissemination of Information in Optical Networks: From Technology to Algorithms
Subir Bandyopadhyay (in cooperation with Ralf Klasing)
Springer Monograph Springer-Verlag, 2008
[Paper]
- Dissemination of Information in Communication Networks: Part I. Broadcasting, Gossiping, Leader Election, and Fault-Tolerance
J. Hromkovič, R. Klasing, A. Pelc, P. Ružička, and W. Unger
Springer Monograph Springer-Verlag, 2005
[Paper]
- Graphs and Algorithms in Communication Networks
Ioannis Caragiannis, Michele Flammini, Christos Kaklamanis, Ralf Klasing, and Alfredo Navarra
Arie Koster and Xavier Munoz, editors
Chapter Energy Consumption Minimization in Ad Hoc Wireless and Multi-Interface Networks, pp. 335--355
Springer Monograph Springer-Verlag, 2010
[Paper]
- Graphs and Algorithms in Communication Networks
Vincenzo Bonifaci, Ralf Klasing, Peter Korteweg, Leen Stougie, and Alberto Marchetti-Spaccamela
Arie Koster and Xavier Munoz, editors
Chapter Data Gathering in Wireless Networks, pp. 357--377
Springer Monograph Springer-Verlag, 2010
[Paper]
- Combinatorial Network Theory
J. Hromkovič, R. Klasing, B. Monien, and R. Peine
Frank Hsu and Ding-Zhu Du, editors
Chapter Dissemination of Information in Interconnection Networks (Broadcasting and Gossiping), pp. 125--212
Kluwer Academic Publishers, 1996
- Computer Science Today: Recent Trends and Developments
B. Monien, R. Diekmann, R. Feldmann, R. Klasing, R. Lüling, K. Menzel, T. Römke, and U.-P. Schroeder
Jan vanLeeuwen, editor
volume 1000 of Lecture Notes in Computer Science, Chapter Efficient Use of Parallel & Distributed Systems: From Theory to Practice, pp. 62--77
Springer, 1995
[Paper]
- Locating and repairing faults in a network with mobile agents
Colin Cooper, Ralf Klasing, and Tomasz Radzik
Theoretical Computer Science, 411(14--15):1638--1647, Mar. 2010
[Paper]
- On the Size of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks
Juraj Hromkovič, Przemyslawa Kanarek, Ralf Klasing, Krzysztof Lorys, Walter Unger, and Hubert Wagener
SIAM Journal on Discrete Mathematics, 23(3):1612--1645, 2009
[Paper]
- From Balls and Bins to Points and Vertices
Ralf Klasing, Zvi Lotker, Alfredo Navarra, and Stéphane Pérennes
Algorithmic Operations Research, 4(2):133--143, 2009
[Paper]
- On the Complexity of Distributed Graph Coloring with Local Minimality Constraints
Cyril Gavoille, Ralf Klasing, Adrian Kosowski, Lukasz Kuszner, and Alfredo Navarra
Networks, 54(1):12--19, Aug. 2009
[Paper]
- Cost Minimisation in Wireless Networks with a Bounded and Unbounded Number of Interfaces
Ralf Klasing, Adrian Kosowski, and Alfredo Navarra
Networks, 53(3):266--275, May 2009
[Paper]
- On k-Connectivity Problems with Sharpened Triangle Inequality
Hans-Joachim Böckenhauer, Dirk Bongartz, Juraj Hromkovič, Ralf Klasing, Guido Proietti, Sebastian Seibert, and Walter Unger
Journal of Discrete Algorithms, 6(4):605--617, Dec. 2008
[Paper]
- Fast Periodic Graph Exploration with Constant Memory
Leszek Gasieniec, Ralf Klasing, Russell Martin, Alfredo Navarra, and Xiaohui Zhang
Journal of Computer and System Sciences, 74(5):808--822, Aug. 2008
[Paper]
- Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
Sylvain Gravier, Ralf Klasing, and Julien Moncel
Algorithmic Operations Research, 3(1):43--50, 2008
[Paper]
- On the Complexity of Bandwidth Allocation in Radio Networks
Ralf Klasing, Nelson Morales, and Stéphane Pérennes
Theoretical Computer Science, 406(3):225--239, Oct. 2008
[Paper]
- A randomized algorithm for the joining protocol in dynamic distributed networks
Colin Cooper, Ralf Klasing, and Tomasz Radzik
Theoretical Computer Science, 406(3):248--262, Oct. 2008
[Paper]
- Approximation bounds for Black Hole Search problems
Ralf Klasing, Euripides Markou, Tomasz Radzik, and Fabiano Sarracco
Networks, 52(4):216--226, Dec. 2008
[Paper]
- Tightening the upper bound for the Minimum Energy Broadcasting
Michele Flammini, Ralf Klasing, Alfredo Navarra, and Stéphane Pérennes
Wireless Networks, 14(5):659--669, October 2008
[Paper]
- Gathering asynchronous oblivious mobile robots in a ring
Ralf Klasing, Euripides Markou, and Andrzej Pelc
Theoretical Computer Science, 390(1):27--39, Jan. 2008
[Paper]
- Improved approximation results for the Minimum Energy Broadcasting problem in Wireless Ad Hoc Networks
Michele Flammini, Ralf Klasing, Alfredo Navarra, and Stéphane Pérennes
Algorithmica, 49(4):318--336, December 2007
[Paper]
- Hardness and approximation results for black hole search in arbitrary graphs
Ralf Klasing, Euripides Markou, Tomasz Radzik, and Fabiano Sarracco
Theoretical Computer Science, 384(2--3):201--221, Oct. 2007
[Paper]
- Constructing Incremental Sequences in Graphs
Ralf Klasing, Christian Laforest, Joseph G. Peters, and Nicolas Thibault
Algorithmic Operations Research, 1(2):1--7, 2006
[Paper]
- Hardness and approximation of Gathering in static radio networks
Jean-Claude Bermond, Jér\^ome Galtier, Ralf Klasing, Nelson Morales, and Stéphane P\' erennes
Parallel Processing Letters, 16(2):165--183, June 2006
[Paper]
- Lower Bounds and Algorithms for Dominating Sets in Web Graphs
Colin Cooper, Ralf Klasing, and Michele Zito
Internet Mathematics, 2(3):275--300, 2005
[Paper]
- On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
H.-J. Böckenhauer, D. Bongartz, J. Hromkovič, R. Klasing, G. Proietti, S. Seibert, and W. Unger
Theoretical Computer Science, 326(1--3):137--153, Oct. 2004
[Paper]
- Hardness results and approximation algorithms of k-tuple domination in graphs
R. Klasing and C. Laforest
Information Processing Letters, 89(2):75--83, Jan. 2004
[Paper]
- Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem
H.-J. Böckenhauer, J. Hromkovič, R. Klasing, S. Seibert, and W. Unger
Theoretical Computer Science, 285(1):3--24, Aug. 2002
[Paper]
- Approximation algorithms for the TSP with sharpened triangle inequality
H.-J. Böckenhauer, J. Hromkovič, R. Klasing, S. Seibert, and W. Unger
Information Processing Letters, 75(3):133--138, Aug. 2000
[Paper]
- Improved Compressions of Cube-Connected Cycles Networks
R. Klasing
IEEE Transactions on Parallel and Distributed Systems, 9(8):803--812, Aug. 1998
[Paper]
- Compressing cube-connected cycles and butterfly networks
R. Klasing, R. Lüling, and B. Monien
Networks, 32(1):47--65, Aug. 1998
[Paper]
- Effective Systolic Algorithms for Gossiping in Cycles
J. Hromkovič, R. Klasing, D. Pardubská, J. Waczulík, and H. Wagener
Parallel Processing Letters, 8(2):197--205, June 1998
[Paper]
- The Relationship between the Gossip Complexity in Vertex-Disjoint Paths Mode and the Vertex Bisection Width
R. Klasing
Discrete Applied Mathematics, 83(1-3):229--246, Mar. 1998
[Paper]
- Optimal Embedding of Complete Binary Trees into Lines and Grids
R. Heckmann, R. Klasing, B. Monien, and W. Unger
Journal of Parallel and Distributed Computing, 49(1):40--56, Feb. 1998
[Paper]
- Optimal Algorithms for Broadcast and Gossip in the Edge-Disjoint Path Modes
J. Hromkovič, R. Klasing, W. Unger, and H. Wagener
Information and Computation, 133(1):1--33, Feb. 1997
[Paper]
- Dissemination of information in vertex-disjoint paths mode
J. Hromkovič, R. Klasing, and E.A. Stöhr
Computers and Artificial Intelligence, 15(4):295--318, 1996
[Paper]
- Gossiping in Vertex-Disjoint Paths Mode in d-Dimensional Grids and Planar Graphs
J. Hromkovič, R. Klasing, E. Stöhr, and H. Wagener
Information and Computation, 123(1):17--28, Nov. 1995
[Paper]
- Broadcasting in Butterfly and deBruijn Networks
R. Klasing, B. Monien, R. Peine, and E. Stöhr
Discrete Applied Mathematics, 53(1-3):183--197, Sep. 1994
[Paper]
- The Complexity of Systolic Dissemination of Information in Interconnection Networks
J. Hromkovič, R. Klasing, W. Unger, H. Wagener, and D. Pardubská
R.A.I.R.O. Theoretical Informatics and Applications, 28(3-4):303--342, 1994
[Paper]
- Improved Approximations for TSP with Simple Precedence Constraints
Hans-Joachim Böckenhauer, Ralf Klasing, Tobias Mömke, and Monika Steinova
In Proceedings of the 7th International Conference on Algorithms and Complexity (CIAC 2010), Lecture Notes in Computer Science Springer Verlag, 2010
to appear
[Paper]
- Robustness of the rotor-router mechanism
Evangelos Bampas, Leszek Gasieniec, Ralf Klasing, Adrian Kosowski, and Tomasz Radzik
In Proceedings of the 13th International Conference on Principles of Distributed Systems (OPODIS 2009), volume 5923 of Lecture Notes in Computer Science, pp. 345--358 Springer Verlag, December 2009
[Paper]
- Euler tour lock-in problem in the rotor-router model
Evangelos Bampas, Leszek Gasieniec, Nicolas Hanusse, David Ilcinkas, Ralf Klasing, and Adrian Kosowski
In Proceedings of the 23rd International Symposium on Distributed Computing (DISC 2009), volume 5805 of Lecture Notes in Computer Science, pp. 423--435 Springer Verlag, September 2009
[Paper]
- Derandomizing Random Walks in Undirected Graphs Using Locally Fair Exploration Strategies
Colin Cooper, David Ilcinkas, Ralf Klasing, and Adrian Kosowski
In Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), volume 5556 of Lecture Notes in Computer Science, pp. 411--422 Springer Verlag, July 2009
[Paper]
- More efficient periodic traversal in anonymous undirected graphs
Jurek Czyzowicz, Stefan Dobrev, Leszek Gasieniec, David Ilcinkas, Jesper Jansson, Ralf Klasing, Ioannis Lignos, Russell Martin, Kunihiko Sadakane, and Wing-Kin Sung
In Proceedings of the 16th Colloquium on Structural Information and Communication Complexity (SIROCCO 2009), volume 5869 of Lecture Notes in Computer Science, pp. 174--188 Springer Verlag, May 2009
[Paper]
- Taking Advantage of Symmetries: Gathering of Asynchronous Oblivious Robots on a Ring
Ralf Klasing, Adrian Kosowski, and Alfredo Navarra
In Proceedings of the 12th International Conference on Principles of Distributed Systems (OPODIS 2008), volume 5401 of Lecture Notes in Computer Science, pp. 446--462 Springer Verlag, December 2008
[Paper]
- Locating and repairing faults in a network with mobile agents
Colin Cooper, Ralf Klasing, and Tomasz Radzik
In Proceedings of the 15th Colloquium on Structural Information and Communication Complexity (SIROCCO 2008), volume 5058 of Lecture Notes in Computer Science, pp. 20--32 Springer Verlag, June 2008
[Paper]
- On the Complexity of Distributed Greedy Coloring
Cyril Gavoille, Ralf Klasing, Adrian Kosowski, and Alfredo Navarra
In Proceedings of the 21st International Symposium on Distributed Computing (DISC 2007), volume 4731 of Lecture Notes in Computer Science, pp. 482--484 Springer Verlag, September 2007
[Paper]
- Fast Periodic Graph Exploration with Constant Memory
Leszek Gasieniec, Ralf Klasing, Russell Martin, Alfredo Navarra, and Xiaohui Zhang
In Proceedings of the 14th Colloquium on Structural Information and Communication Complexity (SIROCCO 2007), volume 4474 of Lecture Notes in Computer Science, pp. 26--40 Springer Verlag, June 2007
[Paper]
- Cost minimisation in multi-interface networks
Ralf Klasing, Adrian Kosowski, and Alfredo Navarra
In Proceedings of the 1st Annual International Conference on Network Control and Optimization (NET-COOP 2007), volume 4465 of Lecture Notes in Computer Science, pp. 276--285 Springer Verlag, June 2007
[Paper]
- Gathering asynchronous oblivious mobile robots in a ring
Ralf Klasing, Euripides Markou, and Andrzej Pelc
In Proceedings of the 17th Annual International Symposium on Algorithms and Computation (ISAAC 2006), volume 4288 of Lecture Notes in Computer Science, pp. 744--753 Springer Verlag, December 2006
[Paper]
- Gathering in specific radio networks
Jean-Claude Bermond, Jér\^ome Galtier, Ralf Klasing, Nelson Morales, and Stéphane Pérennes
In 8èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel06), Trégastel, pp. 85--88, May 2006
[Paper]
- Hardness and approximation of Gathering in static radio networks
Jean-Claude Bermond, Jér\^ome Galtier, Ralf Klasing, Nelson Morales, and Stéphane Pérennes
In FAWN06, Pisa, Italy, pp. 75--79, March 2006
[Paper]
- Searching for black-hole faults in a network using multiple agents
Colin Cooper, Ralf Klasing, and Tomasz Radzik
In Proceedings of the 10th International Conference on Principles of Distributed Systems (OPODIS 2006), volume 4305 of Lecture Notes in Computer Science, pp. 320--332 Springer Verlag, December 2006
[Paper]
- Approximation bounds for Black Hole Search problems
Ralf Klasing, Euripides Markou, Tomasz Radzik, and Fabiano Sarracco
In Proceedings of the 9th International Conference on Principles of Distributed Systems (OPODIS 2005), volume 3974 of Lecture Notes in Computer Science, pp. 261--274 Springer Verlag, 2006
[Paper]
- From Balls and Bins to Points and Vertices
Ralf Klasing, Zvi Lotker, Alfredo Navarra, and Stéphane Pérennes
In Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005), volume 3827 of Lecture Notes in Computer Science, pp. 757--766 Springer Verlag, December 2005
[Paper]
- Hardness and approximation results for black hole search in arbitrary graphs
Ralf Klasing, Euripides Markou, Tomasz Radzik, and Fabiano Sarracco
In Proceedings of the 12th Colloquium on Structural Information and Communication Complexity (SIROCCO 2005), volume 3499 of Lecture Notes in Computer Science, pp. 200--215 Springer Verlag, May 2005
[Paper]
- Dominating Sets in Web Graphs
C. Cooper, R. Klasing, and M. Zito
In Algorithms and Models for the Web-Graph: Third International Workshop, WAW 2004, volume 3243 of Lecture Notes in Computer Science, pp. 31--43 Springer-Verlag, Oct. 2004
[Paper]
- Improved approximation results for the Minimum Energy Broadcasting Problem
M. Flammini, R. Klasing, A. Navarra, and S. Pérennes
In Workshop on Discrete Algorithms and Methods for MOBILE Computing and Communications, Proceedings of the 2004 joint workshop on Foundations of mobile computing, pp. 85--91 ACM Press, Oct. 2004
[Paper]
- Adaptive Broadcast Consumption (ABC), a new heuristic and new bounds for the Minimum Energy Broadcast Routing Problem
R. Klasing, A. Navarra, A. Papadopoulos, and S. Pérennes
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, pp. 866--877 Springer-Verlag, May 2004
[Paper]
- On k-Edge-Connectivity Problems with Sharpened Triangle Inequality (Extended Abstract)
H.-J. Böckenhauer, D. Bongartz, J. Hromkovič, R. Klasing, G. Proietti, S. Seibert, and W. Unger
In Algorithms and Complexity: 5th Italian Conference, CIAC 2003, volume 2653 of Lecture Notes in Computer Science, pp. 189--200 Springer-Verlag, May 2003
[Paper]
- On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality (Extended Abstract)
H.-J. Böckenhauer, D. Bongartz, J. Hromkovič, R. Klasing, G. Proietti, S. Seibert, and W. Unger
In FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science: 22nd Conference, volume 2556 of Lecture Notes in Computer Science, pp. 59--70 Springer-Verlag, Dec. 2002
[Paper]
- Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem
H.-J. Böckenhauer, J. Hromkovič, R. Klasing, S. Seibert, and W. Unger
In Algorithms and Complexity: 4th Italian Conference, CIAC 2000, volume 1767 of Lecture Notes in Computer Science, pp. 72--86 Springer-Verlag, Mar. 2000
[Paper]
- An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality
H.-J. Böckenhauer, J. Hromkovič, R. Klasing, S. Seibert, and W. Unger
In STACS 2000: 17th Annual Symposium on Theoretical Aspects of Computer Science, volume 1770 of Lecture Notes in Computer Science, pp. 382--394 Springer-Verlag, Feb. 2000
[Paper]
- Improved Compressions of Cube-Connected Cycles Networks
R. Klasing
In 24rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG '98), volume 1517 of Lecture Notes in Computer Science, pp. 242--256 Springer-Verlag, June 1998
[Paper]
- Effective Systolic Algorithms for Gossiping in Cycles and Two-Dimensional Grids (Extended Abstract)
J. Hromkovič, R. Klasing, D. Pardubská, W. Unger, J. Waczulík, and H. Wagener
In H. Reichel, editor, Fundamentals of Computation Theory, 10th International Symposium, FCT '95, volume 965 of Lecture Notes in Computer Science, pp. 273--282 Springer, Aug. 1995
[Paper]
- On the Sizes of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks
J. Hromkovič, K. Lorys, P. Kanarek, R. Klasing, W. Unger, and H. Wagener
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, pp. 255--266 Springer, Mar. 1995
[Paper]
- The Complexity of Systolic Dissemination of Information in Interconnection Networks
J. Hromkovič, R. Klasing, W. Unger, H. Wagener, and D. Pardubská
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, pp. 235--249 Springer, May 1994
[Paper]
- The Relationship Between Gossiping in Vertex-Disjoint Paths Mode and Bisection Width
R. Klasing
In I. Pr\'\ivara, 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, pp. 473--483 Springer, Aug. 1994
[Paper]
- Optimal Algorithms for Broadcast and Gossip in the Edge-Disjoint Path Modes (Extended Abstract)
J. Hromkovič, R. Klasing, W. Unger, and H. Wagener
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, pp. 219--230 Springer, July 1994
[Paper]
- Gossiping in Vertex-Disjoint Paths Mode in d-Dimensional Grids and Planar Graphs
Juraj Hromkovič, Ralf Klasing, Elena A. Stöhr, and Hubert Wagener
In T. Lengauer, editor, Algorithms - ESA '93, First Annual European Symposium, volume 726 of Lecture Notes in Computer Science, pp. 200--211 Springer, Oct. 1993
[Paper]
- Gossiping in Vertex-Disjoint Path Mode in Interconnection Networks
Juraj Hromkovič, Ralf Klasing, and Elena A. Stöhr
In J. vanLeeuwen, editor, Graph-Theoretic Concepts in Computer Science, 19th International Workshop, WG '93, volume 790 of Lecture Notes in Computer Science, pp. 288--300 Springer, June 1993
[Paper]
- Parallel Architectures: Design and Efficient Use
Burkhard Monien, Rainer Feldmann, Ralf Klasing, and Reinhard Lüling
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, pp. 247--269 Springer, Feb. 1993
Invited Talk
[Paper]
- Broadcasting in Butterfly and DeBruijn Networks
Ralf Klasing, Burkhard Monien, Regine Peine, and Elena A. Stöhr
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, pp. 351--362 Springer, Feb. 1992
[Paper]
- Optimal Embedding of Complete Binary Trees into Lines and Grids
Ralf Heckmann, Ralf Klasing, Burkhard Monien, and Walter Unger
In G. Schmidt and R. Berghammer, editors, 17th International Workshop, WG '91, volume 570 of Lecture Notes in Computer Science, pp. 25--35 Springer, June 1991
[Paper]
- Compressing cube-connected cycles and butterfly networks
Ralf Klasing, Reinhard Lüling, and Burkhard Monien
In 2nd IEEE Symposium on Parallel and Distributed Processing, SPDP '90, pp. 858--865, Dec. 1990
[Paper]
- On the Complexity of Distributed Graph Coloring with Local Minimality Constraints
Cyril Gavoille, Ralf Klasing, Adrian Kosowski, \Lukasz Kuszner, and Alfredo Navarra
Technical Report RR-1440-07, LaBRI, December 2007
appears also as INRIA Research Report RR-6399, December 2007
[Paper]
- From Balls and Bins to Points and Vertices
Ralf Klasing, Zvi Lotker, Alfredo Navarra, and Stéphane Pérennes
Technical Report RR-1437-07, LaBRI, October 2007
[Paper]
- Cost Minimisation in Wireless Networks with a Bounded and Unbounded Number of Interfaces
Ralf Klasing, Adrian Kosowski, and Alfredo Navarra
Technical Report RR-1436-07, LaBRI, September 2007
[Paper]
- A randomized algorithm for the joining protocol in dynamic distributed networks
Colin Cooper, Ralf Klasing, and Tomasz Radzik
Technical Report RR-1432-07, LaBRI, June 2007
[Paper]
- On k-Connectivity Problems with Sharpened Triangle Inequality
Hans-Joachim Böckenhauer, Dirk Bongartz, Juraj Hromkovič, Ralf Klasing, Guido Proietti, Sebastian Seibert, and Walter Unger
Technical Report RR-1430-07, LaBRI, May 2007
[Paper]
- Fast Periodic Graph Exploration with Constant Memory
Leszek Gasieniec, Ralf Klasing, Russell Martin, Alfredo Navarra, and Xiaohui Zhang
Technical Report RR-1426-07, LaBRI, April 2007
[Paper]
- Gathering asynchronous oblivious mobile robots in a ring
Ralf Klasing, Euripides Markou, and Andrzej Pelc
Technical Report RR-1422-07, LaBRI, January 2007
[Paper]
- Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
Sylvain Gravier, Ralf Klasing, and Julien Moncel
Technical Report RR-1417-06, LaBRI, November 2006
[Paper]
- On the Size of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks
Juraj Hromkovič, Przemyslawa Kanarek, Ralf Klasing, Krzysztof Lorys, Walter Unger, and Hubert Wagener
Technical Report RR-1410-06, LaBRI, September 2006
[Paper]
- Approximation bounds for Black Hole Search problems
Ralf Klasing, Euripides Markou, Tomasz Radzik, and Fabiano Sarracco
Technical Report RR-1407-06, LaBRI, July 2006
appears also as INRIA Research Report RR-6185, May 2007
[Paper]
- Hardness and approximation of Gathering in static radio networks
Jean-Claude Bermond, Jér\^ome Galtier, Ralf Klasing, Nelson Morales, and Stéphane Pérennes
Technical report, INRIA Research Report RR-5936 and LaBRI Research Report RR-1403-06, June 2006
[Paper]
- Lower Bounds and Algorithms for Dominating Sets in Web Graphs
C. Cooper, R. Klasing, and M. Zito
Technical report, INRIA Research Report RR-5529 and I3S Research Report I3S/RR-2005-09-FR, 2005
- Constructing Incremental Sequences in Graphs
R. Klasing, C. Laforest, J. Peters, and N. Thibault
Research report, INRIA Research Report RR-5648 and I3S Research Report I3S/RR-2005-22-FR, 2005
- Approximation Results for Black Hole Search in Arbitrary Networks
R. Klasing, E. Markou, T. Radzik, and F. Sarracco
Research report, INRIA Research Report RR-5659 and I3S Research Report I3S/RR-2005-23-FR, 2005
- The Points and Vertices Game
R. Klasing, Z. Lotker, A. Navarra, and S. Pérennes
Technical Report TRCS 030/2004, Dipartimento di Informatica, Università degli Studi di L'Aquila, 2004
[Paper]
- Complexity of Bandwidth Allocation in Radio Networks: the static case
R. Klasing, N. Morales, and S. Pérennes
Research report, INRIA Research Report RR-5432 and I3S Research Report I3S/RR-2004-40-FR, 2004
[Paper]
- A randomized algorithm for the joining protocol in dynamic distributed networks
C. Cooper, R. Klasing, and T. Radzik
Research report, INRIA Research Report RR-5376 and I3S Research Report I3S/RR-2004-39-FR, 2004
[Paper]
- Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem
H.-J. Böckenhauer, J. Hromkovič, R. Klasing, S. Seibert, and W. Unger
Research Report TR99-031, Electronic Colloquium on Computational Complexity (ECCC), Sep. 1999
[Paper]
Automatically generated on 2010-03-04 at 20:31