Dr Ralf Klasing - Publications sorted by date

2017

  1.  Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Bordeaux, France, September 11-13, 2017, Proceedings
    Ralf Klasing and Marc Zeitoun, editors
    volume 10472 of ARCoSS Lecture Notes in Computer Science Springer, 2017
    [Paper]
  2.  Algorithms for Sensor Systems - 12th International Symposium, ALGOSENSORS 2016, Aarhus, Denmark, August 25-26, 2016, Proceedings
    Marek Chrobak, Antonio Fernandez Anta, Leszek Gasieniec, and Ralf Klasing, editors
    volume 10050 of Lecture Notes in Computer Science Springer, 2017
    [Paper]
  3.  Approximability and inapproximability of the star p-hub center problem with parameterized triangle inequality
    Li-Hsuan Chen, Dun-Wei Cheng, Sun-Yuan Hsieh, Ling-Ju Hung, Ralf Klasing, Chia-Wei Lee, and Bang Ye Wu
    Journal of Computer and System Sciences, 2017
    [Paper]
  4.  Parameterized and approximation complexity of the detection pair problem in graphs
    Florent Foucaud and Ralf Klasing
    Journal of Graph Algorithms and Applications, 21(6):1039--1056, 2017
    [Paper]
  5.  Robustness of the rotor-router mechanism
    Evangelos Bampas, Leszek Gasieniec, Nicolas Hanusse, David Ilcinkas, Ralf Klasing, Adrian Kosowski, and Tomasz Radzik
    Algorithmica, 78(3):869--895, Jul 2017
    [Paper]
  6.  The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks
    Ralf Klasing, Adrian Kosowski, Dominik Pajak, and Thomas Sauerwald
    Distributed Computing, 30(2):127--148, 2017
    [Paper]
  7.  Collision-Free Network Exploration
    Jurek Czyzowicz, Dariusz Dereniowski, Leszek Gasieniec, Ralf Klasing, Adrian Kosowski, and Dominik Pajak
    Journal of Computer and System Sciences, 86:70--81, 2017
    [Paper]
  8.  The approximability of the p-hub center problem with parameterized triangle inequality
    Li-Hsuan Chen, Sun-Yuan Hsieh, Ling-Ju Hung, and Ralf Klasing
    In Proceedings of the 23rd International Computing and Combinatorics Conference (COCOON 2017), volume 10392 of Lecture Notes in Computer Science, pp. 112--123 Springer Verlag, 2017
    [Paper]
  9.  A Generic Framework for Computing Parameters of Sequence-based Dynamic Graphs
    Arnaud Casteigts, Ralf Klasing, Yessin M. Neggaz, and Joseph G. Peters
    In Proceedings of the 24th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2017), volume 10641 of Lecture Notes in Computer Science Springer Verlag, 2017
    [Paper]
  10.  On the complexity of the star p-hub center problem with parameterized triangle inequality
    Li-Hsuan Chen, Sun-Yuan Hsieh, Ling-Ju Hung, Ralf Klasing, Chia-Wei Lee, and Bang Ye Wu
    In Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC 2017), volume 10236 of Lecture Notes in Computer Science, pp. 152--163 Springer Verlag, 2017
    [Paper]
  11.  Bamboo Garden Trimming Problem (Perpetual maintenance of machines with different attendance urgency factors)
    Leszek Gasieniec, Ralf Klasing, Christos Levcopoulos, Andrzej Lingas, Jie Min, and Tomasz Radzik
    In Proceedings of the 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2017), volume 10139 of Lecture Notes in Computer Science, pp. 229--240 Springer Verlag, 2017
    [Paper]
  12.  Calcul de Paramètres Minimaux dans les Graphes Dynamiques
    Arnaud Casteigts, Ralf Klasing, Yessin M. Neggaz, and Joseph G. Peters
    In ALGOTEL 2017 - 19èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Quiberon, France, 2017
    [Paper]

2016

  1.  Gathering of Robots on Anonymous Grids without Multiplicity Detection
    Gianlorenzo D'Angelo, Gabriele Di Stefano, Ralf Klasing, and Alfredo Navarra
    Theoretical Computer Science, 610:158--168, 2016
    [Paper]
  2.  Setting Ports in an Anonymous Network: How to Reduce the Level of Symmetry?
    Ralf Klasing, Adrian Kosowski, and Dominik Pajak
    In Proceedings of the 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO 2016), volume 9988 of Lecture Notes in Computer Science, pp. 35--48 Springer Verlag, 2016
    [Paper]
  3.  Linear search by a pair of distinct-speed robots
    Evangelos Bampas, Jurek Czyzowicz, Leszek Gasieniec, David Ilcinkas, Ralf Klasing, Tomasz Kociumaka, and Dominik Pajak
    In Proceedings of the 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO 2016), volume 9988 of Lecture Notes in Computer Science, pp. 195--211 Springer Verlag, 2016
    [Paper]

2015

  1.  Rendezvous of Heterogeneous Mobile Agents in Edge-Weighted Networks
    Dariusz Dereniowski, Ralf Klasing, Adrian Kosowski, and Lukasz Kuszner
    Theoretical Computer Science, 608:219--230, 2015
    [Paper]
  2.  Network Verification via Routing Table Queries
    Evangelos Bampas, Davide Bil\`o, Guido Drovandi, Luciano Gualà, Ralf Klasing, and Guido Proietti
    Journal of Computer and System Sciences, 81(1):234--248, 2015
    [Paper]
  3.  Beachcombing on Strips and Islands
    Evangelos Bampas, Jurek Czyzowicz, David Ilcinkas, and Ralf Klasing
    In Proceedings of the 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS 2015), volume 9536 of Lecture Notes in Computer Science, pp. 155--168 Springer Verlag, 2015
    [Paper]
  4.  Improved Analysis of Deterministic Load-Balancing Schemes
    Petra Berenbrink, Ralf Klasing, Adrian Kosowski, Frederik Mallmann-Trenn, and Przemyslaw Uznanski
    In Proceedings of the 34th ACM Symposium on Principles of Distributed Computing (PODC 2015), pp. 301--310, July 2015
    [Paper]
  5.  Efficiently Testing T-Interval Connectivity in Dynamic Graphs
    Arnaud Casteigts, Ralf Klasing, Yessin M. Neggaz, and Joseph G. Peters
    In Proceedings of the 9th International Conference on Algorithms and Complexity (CIAC 2015), volume 9079 of Lecture Notes in Computer Science, pp. 89--100 Springer Verlag, 2015
    [Paper]
  6.  Tester efficacement la T-intervalle connexité dans les graphes dynamiques
    Arnaud Casteigts, Ralf Klasing, Yessin M. Neggaz, and Joseph G. Peters
    In ALGOTEL 2015 - 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Beaune, France, June 2015
    [Paper]

2014

  1.  Selected Papers from the 11th International Symposium on Experimental Algorithms (SEA 2012)
    Ralf Klasing, editor
    volume 19 of ACM Journal of Experimental Algorithmics, Dec. 2014
    [Paper]
  2.  Centroidal bases in graphs
    Florent Foucaud, Ralf Klasing, and Peter J. Slater
    Networks, 64(2):96--108, 2014
    [Paper]
  3.  Exploration of Constantly Connected Dynamic Graphs Based on Cactuses
    David Ilcinkas, Ralf Klasing, and Ahmed Mouhamadou Wade
    In Proceedings of the 21th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2014), volume 8576 of Lecture Notes in Computer Science, pp. 250--262 Springer Verlag, 2014
    [Paper]
  4.  Rendezvous of Heterogeneous Mobile Agents in Edge-Weighted Networks
    Dariusz Dereniowski, Ralf Klasing, Adrian Kosowski, and Lukasz Kuszner
    In Proceedings of the 21th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2014), volume 8576 of Lecture Notes in Computer Science, pp. 311--326 Springer Verlag, 2014
    [Paper]
  5.  Collision-Free Network Exploration
    Jurek Czyzowicz, Dariusz Dereniowski, Leszek Gasieniec, Ralf Klasing, Adrian Kosowski, and Dominik Pajak
    In Proceedings of the 11th Latin American Theoretical Informatics Symposium (LATIN 2014), volume 8392 of Lecture Notes in Computer Science, pp. 342--354 Springer Verlag, 2014
    [Paper]

2013

  1.  Gathering radio messages in the path
    Jean-Claude Bermond, Ralf Klasing, Nelson Morales, Stéphane Pérennes, and Patricio Reyes
    Discrete Mathematics, Algorithms and Applications, 5(1), Mar. 2013
    [Paper]
  2.  Efficient Exploration of Anonymous Undirected Graphs
    Ralf Klasing
    In Proceedings of the 24th International Workshop on Combinatorial Algorithms (IWOCA 2013), volume 8288 of Lecture Notes in Computer Science, pp. 7--13 Springer Verlag, July 2013
    [Paper]
  3.  The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks
    Ralf Klasing, Adrian Kosowski, Dominik Pajak, and Thomas Sauerwald
    In Proceedings of the 32nd ACM Symposium on Principles of Distributed Computing (PODC 2013), pp. 365--374, July 2013
    [Paper]

2012

  1.  Experimental Algorithms - 11th International Symposium, SEA 2012, Bordeaux, France, June 7-9, 2012. Proceedings
    Ralf Klasing, editor
    volume 7276 of Lecture Notes in Computer Science Springer, 2012
    [Paper]
  2.  On the size of identifying codes in triangle-free graphs
    Florent Foucaud, Ralf Klasing, Adrian Kosowski, and André Raspaud
    Discrete Applied Mathematics, 160(10--11):1532--1546, July 2012
    [Paper]
  3.  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
    Theoretical Computer Science, 444:60--76, July 2012
    [Paper]
  4.  Gathering of Robots on Anonymous Grids without Multiplicity Detection
    Gianlorenzo D'Angelo, Gabriele Di Stefano, Ralf Klasing, and Alfredo Navarra
    In Proceedings of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012), volume 7355 of Lecture Notes in Computer Science, pp. 327--338 Springer Verlag, June 2012
    [Paper]

2011

  1.  Derandomizing Random Walks in Undirected Graphs Using Locally Fair Exploration Strategies
    Colin Cooper, David Ilcinkas, Ralf Klasing, and Adrian Kosowski
    Distributed Computing, 24(2):91--99, Oct. 2011
    [Paper]
  2.  Network Verification via Routing Table Queries
    Evangelos Bampas, Davide Bil\`o, Guido Drovandi, Luciano Gualà, Ralf Klasing, and Guido Proietti
    In Proceedings of the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2011), volume 6796 of Lecture Notes in Computer Science, pp. 270--281 Springer Verlag, June 2011
    [Paper]

2010

  1.  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]
  2.  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]
  3.  Taking Advantage of Symmetries: Gathering of many Asynchronous Oblivious Robots on a Ring
    Ralf Klasing, Adrian Kosowski, and Alfredo Navarra
    Theoretical Computer Science, 411(34--36):3235--3246, July 2010
    [Paper]
  4.  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]
  5.  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), volume 6078 of Lecture Notes in Computer Science, pp. 61--72 Springer Verlag, 2010
    [Paper]

2009

  1.  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]
  2.  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]
  3.  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]
  4.  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]
  5.  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]
  6.  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]
  7.  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]
  8.  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]

2008

  1.  Dissemination of Information in Optical Networks: From Technology to Algorithms
    Subir Bandyopadhyay (in cooperation with Ralf Klasing)
    Springer Monograph Springer-Verlag, 2008
    [Paper]
  2.  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]
  3.  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]
  4.  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]
  5.  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]
  6.  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]
  7.  Approximation bounds for Black Hole Search problems
    Ralf Klasing, Euripides Markou, Tomasz Radzik, and Fabiano Sarracco
    Networks, 52(4):216--226, Dec. 2008
    [Paper]
  8.  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]
  9.  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]
  10.  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]
  11.  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]

2007

  1.  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]
  2.  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]
  3.  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]
  4.  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]
  5.  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]
  6.  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]
  7.  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]
  8.  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]
  9.  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]
  10.  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]
  11.  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]
  12.  Gathering asynchronous oblivious mobile robots in a ring
    Ralf Klasing, Euripides Markou, and Andrzej Pelc
    Technical Report RR-1422-07, LaBRI, January 2007
    [Paper]

2006

  1.  Constructing Incremental Sequences in Graphs
    Ralf Klasing, Christian Laforest, Joseph G. Peters, and Nicolas Thibault
    Algorithmic Operations Research, 1(2):1--7, 2006
    [Paper]
  2.  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]
  3.  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]
  4.  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]
  5.  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]
  6.  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]
  7.  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]
  8.  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]
  9.  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]
  10.  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]
  11.  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]

2005

  1.  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]
  2.  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]
  3.  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]
  4.  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]
  5.  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

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

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

2004

  1.  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]
  2.  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]
  3.  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]
  4.  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]
  5.  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]
  6.  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]
  7.  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]
  8.  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]

2003

  1.  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]

2002

  1.  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]
  2.  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]

2000

  1.  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]
  2.  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]
  3.  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]

1999

  1.  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]

1998

  1.  Improved Compressions of Cube-Connected Cycles Networks
    R. Klasing
    IEEE Transactions on Parallel and Distributed Systems, 9(8):803--812, Aug. 1998
    [Paper]
  2.  Compressing cube-connected cycles and butterfly networks
    R. Klasing, R. Lüling, and B. Monien
    Networks, 32(1):47--65, Aug. 1998
    [Paper]
  3.  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]
  4.  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]
  5.  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]
  6.  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]

1997

  1.  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]

1996

  1.  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]
  2.  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

1995

  1.  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]
  2.  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]
  3.  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]
  4.  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]

1994

  1.  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]
  2.  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]
  3.  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]
  4.  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]
  5.  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]

1993

  1.  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]
  2.  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]
  3.  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]

1992

  1.  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]

1991

  1.  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]

1990

  1.  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]

Automatically generated on 2017-11-16 at 19:28