Dr Ralf Klasing - Publications sorted by date

2012

  1.  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, 2012
    to appear

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 2012-01-20 at 16:45