Ralf Klasing

Discret. Appl. Math., 2026

2025

Online Unbounded Knapsack.

[BibT_eX]

[DOI]

Theory Comput. Syst., March, 2025

The g-good-neighbor diagnosability of product networks under the PMC model.

[BibT_eX]

[DOI]

CoRR, March, 2025

Fault-tolerance in distance-edge-monitoring sets.

[BibT_eX]

[DOI]

Acta Informatica, March, 2025

Graph Exploration with Edge Weight Estimates.

[BibT_eX]

[DOI]

Matthias Gehnen

Émile Naquin

CoRR, January, 2025

Monitoring the edges of product networks using distances.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2025

The g-good-neighbor diagnosability of product networks under the PMC model.

[BibT_eX]

[DOI]

Inf. Comput., 2025

Linear programming of monitoring the links of a fractional weighted network using distance.

[BibT_eX]

[DOI]

Wen Li

Yaping Mao

Inf. Comput., 2025

The distance-edge-monitoring numbers of subdivision graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2025

Geographical Peer Matching for P2P Energy Sharing.

[BibT_eX]

[DOI]

Romaric Duvignau

Vincenzo Gulisano

Marina Papatriantafilou

IEEE Access, 2025

2024

Perpetual maintenance of machines with different urgency requirements.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., February, 2024

On the distance-edge-monitoring numbers of graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., January, 2024

Erdös-Gallai-type problems for distance-edge-monitoring numbers.

[BibT_eX]

[DOI]

Discret. Appl. Math., January, 2024

Monitoring the edges of a graph using distances with given girth.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2024

The g-extra connectivity of graph products.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2024

The number of spanning trees for Sierpiński graphs and data center networks.

[BibT_eX]

[DOI]

Inf. Comput., 2024

Perturbation Results for Distance-edge-monitoring Numbers.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2024

Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?

[BibT_eX]

[DOI]

CoRR, 2024

Algorithms and Complexity for Path Covers of Temporal DAGs.

[BibT_eX]

[DOI]

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

Improved Approximation Algorithms for Patrol-Scheduling with Min-Max Latency Using Multiclass Minimum Spanning Forests.

[BibT_eX]

[DOI]

Li-Hsuan Chen

Ling-Ju Hung

Proceedings of the Algorithmic Aspects in Information and Management, 2024

2023

A parallel algorithm for constructing multiple independent spanning trees in bubble-sort networks.

[BibT_eX]

[DOI]

J. Parallel Distributed Comput., November, 2023

Constructing disjoint Steiner trees in Sierpiński graphs.

[BibT_eX]

[DOI]

CoRR, 2023

Greediness is not always a vice: Efficient Discovery Algorithms for Assignment Problems.

[BibT_eX]

[DOI]

Romaric Duvignau

Proceedings of the XII Latin-American Algorithms, Graphs and Optimization Symposium, 2023

Online Knapsack with Removal and Recourse.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 34th International Workshop, 2023

2022

Hardness and approximation for the star p-Hub Routing Cost Problem in metric graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2022

Monitoring the edges of a graph using distances.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2022

On the distance-edge-monitoring numbers of graphs.

[BibT_eX]

[DOI]

CoRR, 2022

Perpetual maintenance of machines with different urgency requirements.

[BibT_eX]

[DOI]

CoRR, 2022

Selected Papers of the 31st International Workshop on Combinatorial Algorithms, IWOCA 2020.

[BibT_eX]

[DOI]

Leszek Gasieniec

Algorithmica, 2022

On the Approximability of the Single Allocation p-Hub Center Problem with Parameterized Triangle Inequality.

[BibT_eX]

[DOI]

Algorithmica, 2022

The Red-Blue Separation Problem on Graphs.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 33rd International Workshop, 2022

2021

The Construction of Multiple Independent Spanning Trees on Burnt Pancake Networks.

[BibT_eX]

[DOI]

IEEE Access, 2021

A Parallel Algorithm for Constructing Multiple Independent Spanning Trees in Bubble-Sort Networks.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Aspects in Information and Management, 2021

2020

Approximation algorithms for the p-hub center routing problem in parameterized metric graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

Selected papers of the 21st International Symposium on Fundamentals of Computation Theory, FCT 2017.

[BibT_eX]

[DOI]

Marc Zeitoun

J. Comput. Syst. Sci., 2020

Vulnerability of super extra edge-connected graphs.

[BibT_eX]

[DOI]

Chia-Wen Cheng

Sun-Yuan Hsieh

J. Comput. Syst. Sci., 2020

IWOCA 2020 in Bordeaux (Oops! On-Line!).

[BibT_eX]

[DOI]

Bull. EATCS, 2020

Top-Down Construction of Independent Spanning Trees in Alternating Group Networks.

[BibT_eX]

[DOI]

IEEE Access, 2020

The Hardness and Approximation of the Densest k-Subgraph Problem in Parameterized Metric Graphs.

[BibT_eX]

[DOI]

Proceedings of the International Computer Symposium, 2020

Monitoring the Edges of a Graph Using Distances.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Discrete Applied Mathematics, 2020

2019

Computing Parameters of Sequence-Based Dynamic Graphs.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2019

2018

Approximability and inapproximability of the star p-hub center problem with parameterized triangle inequality.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2018

Approximation Algorithms for the p-Hub Center Routing Problem in Parameterized Metric Graphs.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 29th International Workshop, 2018

A Modern View on Stability of Approximation.

[BibT_eX]

[DOI]

Tobias Mömke

Proceedings of the Adventures Between Lower Bounds and Higher Altitudes, 2018

2017

Parameterized and approximation complexity of the detection pair problem in graphs.

[BibT_eX]

[DOI]

Florent Foucaud

J. Graph Algorithms Appl., 2017

Robustness of the Rotor-Router Mechanism.

[BibT_eX]

[DOI]

Algorithmica, 2017

Bamboo Garden Trimming Problem (Perpetual Maintenance of Machines with Different Attendance Urgency Factors).

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2017: Theory and Practice of Computer Science, 2017

A Generic Framework for Computing Parameters of Sequence-Based Dynamic Graphs.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2017

The Approximability of the p-hub Center Problem with Parameterized Triangle Inequality.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 23rd International Conference, 2017

On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity - 10th International Conference, 2017

2016

Gathering of robots on anonymous grids and trees without multiplicity detection.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

Setting Ports in an Anonymous Network: How to Reduce the Level of Symmetry?

[BibT_eX]

[DOI]

Dominik Pajak

Proceedings of the Structural Information and Communication Complexity, 2016

Linear Search by a Pair of Distinct-Speed Robots.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2016

2015

Improved Analysis of Deterministic Load-Balancing Schemes.

[BibT_eX]

[DOI]

Petra Berenbrink

Frederik Mallmann-Trenn

Przemyslaw Uznanski

Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

Efficiently Testing T -Interval Connectivity in Dynamic Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity - 9th International Conference, 2015

Beachcombing on Strips and Islands.

[BibT_eX]

[DOI]

Proceedings of the Algorithms for Sensor Systems, 2015

2014

Centroidal bases in graphs.

[BibT_eX]

[DOI]

Florent Foucaud

Peter J. Slater

Networks, 2014

Editorial.

[BibT_eX]

[DOI]

ACM J. Exp. Algorithmics, 2014

Be Fair and Be Selfish! Characterizing Deterministic Diffusive Load-Balancing Schemes with Small Discrepancy.

[BibT_eX]

[DOI]

Petra Berenbrink

Frederik Mallmann-Trenn

Przemyslaw Uznanski

CoRR, 2014

Exploration of Constantly Connected Dynamic Graphs Based on Cactuses.

[BibT_eX]

[DOI]

David Ilcinkas

Ahmed Mouhamadou Wade

Proceedings of the Structural Information and Communication Complexity, 2014

Rendezvous of Heterogeneous Mobile Agents in Edge-Weighted Networks.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2014

Collision-Free Network Exploration.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

2013

Gathering Radio Messages in the Path.

[BibT_eX]

[DOI]

Discret. Math. Algorithms Appl., 2013

The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2013

Efficient Exploration of Anonymous Undirected Graphs.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 24th International Workshop, 2013

2012

On the size of identifying codes in triangle-free graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2012

Gathering of Robots on Anonymous Grids without Multiplicity Detection.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2012

2011

Network Verification via Routing Table Queries.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2011

2010

Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2010

Improved Approximations for TSP with Simple Precedence Constraints.

[BibT_eX]

[DOI]

Alberto Marchetti-Spaccamela

Tobias Mömke

Monika Steinová

Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

Energy Consumption Minimization in Ad Hoc Wireless and Multi-interface Networks.

[BibT_eX]

[DOI]

Proceedings of the Graphs and Algorithms in Communication Networks: Studies in Broadband, 2010

Data Gathering in Wireless Networks.

[BibT_eX]

[DOI]

Proceedings of the Graphs and Algorithms in Communication Networks: Studies in Broadband, 2010

2009

On the Size of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2009

Cost minimization in wireless networks with a bounded and unbounded number of interfaces.

[BibT_eX]

[DOI]

Networks, 2009

On the complexity of distributed graph coloring with local minimality constraints.

[BibT_eX]

[DOI]

Networks, 2009

Euler Tour Lock-In Problem in the Rotor-Router Model.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing, 23rd International Symposium, 2009

More Efficient Periodic Traversal in Anonymous Undirected Graphs.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2009

Robustness of the Rotor-router Mechanism.

[BibT_eX]

[DOI]

Proceedings of the Principles of Distributed Systems, 13th International Conference, 2009

Derandomizing Random Walks in Undirected Graphs Using Locally Fair Exploration Strategies.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th Internatilonal Colloquium, 2009

2008

Tightening the upper bound for the minimum energy broadcasting.

[BibT_eX]

[DOI]

Wirel. Networks, 2008

On the complexity of bandwidth allocation in radio networks.

[BibT_eX]

[DOI]

Nelson Morales

Stéphane Pérennes

Theor. Comput. Sci., 2008

A randomized algorithm for the joining protocol in dynamic distributed networks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2008

On k-connectivity problems with sharpened triangle inequality.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2008

Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs.

[BibT_eX]

[DOI]

Sylvain Gravier

Julien Moncel

Algorithmic Oper. Res., 2008

Locating and Repairing Faults in a Network with Mobile Agents.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2008

Taking Advantage of Symmetries: Gathering of Asynchronous Oblivious Robots on a Ring.

[BibT_eX]

[DOI]

Proceedings of the Principles of Distributed Systems, 12th International Conference, 2008

2007

Hardness and approximation results for Black Hole Search in arbitrary networks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

On the Complexity of Distributed Greedy Coloring.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing, 21st International Symposium, 2007

Fast Periodic Graph Exploration with Constant Memory.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2007

Cost Minimisation in Multi-interface Networks.

[BibT_eX]

[DOI]

Proceedings of the Network Control and Optimization, 2007

2006

Constructing Incremental Sequences in Graphs.

[BibT_eX]

[DOI]

Algorithmic Oper. Res., 2006

Hardness and approximation of Gathering in static radio networks.

[BibT_eX]

[DOI]

Proceedings of the 4th IEEE Conference on Pervasive Computing and Communications Workshops (PerCom 2006 Workshops), 2006

Searching for Black-Hole Faults in a Network Using Multiple Agents.

[BibT_eX]

[DOI]

Proceedings of the Principles of Distributed Systems, 10th International Conference, 2006

Gathering Asynchronous Oblivious Mobile Robots in a Ring.

[BibT_eX]

[DOI]

Euripides Markou

Andrzej Pelc

Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

2005

Lower Bounds and Algorithms for Dominating Sets in Web Graphs.

[BibT_eX]

[DOI]

Michele Zito

Internet Math., 2005

Hardness and Approximation Results for Black Hole Search in Arbitrary Graphs.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2005

Approximation Bounds for Black Hole Search Problems.

[BibT_eX]

[DOI]

Proceedings of the Principles of Distributed Systems, 9th International Conference, 2005

From Balls and Bins to Points and Vertices.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

Dissemination of Information in Communication Networks - Broadcasting, Gossiping, Leader Election, and Fault-Tolerance

[BibT_eX]

[DOI]

Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-540-26663-1, 2005

2004

Hardness results and approximation algorithms of k-tuple domination in graphs.

[BibT_eX]

[DOI]

Christian Laforest

Inf. Process. Lett., 2004

Dominating Sets in Web Graphs.

[BibT_eX]

[DOI]

Michele Zito

Proceedings of the Algorithms and Models for the Web-Graph: Third International Workshop, 2004

Adaptive Broadcast Consumption (ABC), a New Heuristic and New Bounds for the Minimum Energy Broadcast Routing Problem.

[BibT_eX]

[DOI]

Proceedings of the NETWORKING 2004, 2004

Improved approximation results for the minimum energy broadcasting problem.

[BibT_eX]

[DOI]

Proceedings of the DIALM-POMC Joint Workshop on Foundations of Mobile Computing, 2004

2003

On k-Edge-Connectivity Problems with Sharpened Triangle Inequality.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, 5th Italian Conference, 2003

2002

On the Hardness of Constructing Minimal 2-Connected Spanning Subgraphs in Complete Graphs with Sharpened Triangle Inequality.

[BibT_eX]

[DOI]

Proceedings of the FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science, 2002

2000

Approximation algorithms for the TSP with sharpened triangle inequality.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2000

An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality.

[BibT_eX]

[DOI]

Proceedings of the STACS 2000, 2000

Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, 4th Italian Conference, 2000

1998

Effective Systolic Algorithms for Gossiping in Cycles.

[BibT_eX]

[DOI]

Parallel Process. Lett., 1998

The Relationship between the Gossip Complexity in Vertex-Disjoint Paths Mode and the Vertex Bisection Width.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1998

Improved Compressions of Cube-Connected Cycles Networks.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 1998

1997

Optimal Algorithms for Broadcast and Gossip in the Edge-Disjoint Path Modes.

[BibT_eX]

[DOI]

Inf. Comput., 1997

1996

Dissemination of Information in Vertex-Disjoint Paths Mode.

[BibT_eX]

[DOI]

Juraj Hromkovic

Elena Stöhr

Comput. Artif. Intell., 1996

On the Complexity of Broadcast and Gossip in Different Communication Modes.

[BibT_eX]

[DOI]

Verlag Shaker, Aachen, ISBN: 3-8265-1281-2, 1996

1995

On the Sizes of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks.

[BibT_eX]

[DOI]

Proceedings of the STACS 95, 1995

Effective Systolic Algorithms for Gossiping in Cycles and Two-Dimensional Grids (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 10th International Symposium, 1995

Efficient Use of Parallel & Distributed Systems: From Theory to Practice.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Today: Recent Trends and Developments, 1995

1994

Optimal Algorithms for Broadcast and Gossip in the Edge-Disjoint Path Modes (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 1994

The Relationship Between Gossiping in Vertex-Disjoint Paths Mode and Bisection Width.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1994, 1994

The Complexity of Systolic Dissemination of Information in Interconnection Networks.

[BibT_eX]

[DOI]

Proceedings of the Parallel and Distributed Computing, 1994

1993

Gossiping in Vertex-Disjoint Path Mode in Interconnection Networks.

[BibT_eX]

[DOI]

Juraj Hromkovic

Elena Stöhr

Proceedings of the Graph-Theoretic Concepts in Computer Science, 1993

Parallel Architectures: Design and Efficient Use.

[BibT_eX]

[DOI]

Proceedings of the STACS 93, 1993

Gossiping in Vertex-Disjoint Paths Mode in d-Dimensional Grids and Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA '93, First Annual European Symposium, Bad Honnef, Germany, September 30, 1993

1992

Broadcasting in Butterfly and DeBruijn Networks.

[BibT_eX]

[DOI]

Proceedings of the STACS 92, 1992

1991

Optimal Embedding of Complete Binary Trees into Lines and Grids.

[BibT_eX]

[DOI]

Proceedings of the 17th International Workshop, 1991

1990

Compressing cube-connected cycles and butterfly networks.

[BibT_eX]

[DOI]