Ralf Klasing

CoRR, 2024

Online Unbounded Knapsack.

[BibT_eX]

[DOI]

CoRR, 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

The RED-BLUE SEPARATION problem on graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., August, 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 <i>p</i>-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

Monitoring the edges of product networks using distances.

[BibT_eX]

[DOI]

CoRR, 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

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 <i>p</i>-hub center routing problem in parameterized metric graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

Beachcombing on strips and islands.

[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

Improved Analysis of Deterministic Load-Balancing Schemes.

[BibT_eX]

[DOI]

Petra Berenbrink

Frederik Mallmann-Trenn

Przemyslaw Uznanski

ACM Trans. Algorithms, 2019

Computing Parameters of Sequence-Based Dynamic Graphs.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2019

Linear Search by a Pair of Distinct-Speed Robots.

[BibT_eX]

[DOI]

Algorithmica, 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

Collision-free network exploration.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2017

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

[BibT_eX]

[DOI]

Distributed Comput., 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

2015

Rendezvous of heterogeneous mobile agents in edge-weighted networks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Network verification via routing table queries.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2015

Efficiently Testing T -Interval Connectivity in Dynamic Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity - 9th International Conference, 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

2013

Gathering Radio Messages in the Path.

[BibT_eX]

[DOI]

Discret. Math. Algorithms Appl., 2013

Efficient Exploration of Anonymous Undirected Graphs.

[BibT_eX]

[DOI]

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

2012

More efficient periodic traversal in anonymous undirected graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 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

Derandomizing random walks in undirected graphs using locally fair exploration strategies.

[BibT_eX]

[DOI]

Distributed Comput., 2011

2010

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

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2010

Locating and repairing faults in a network with mobile agents.

[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

From Balls and Bins to Points and Vertices.

[BibT_eX]

[DOI]

Algorithmic Oper. Res., 2009

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

[BibT_eX]

[DOI]

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

Robustness of the Rotor-router Mechanism.

[BibT_eX]

[DOI]

Proceedings of the Principles of Distributed Systems, 13th International Conference, 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

Gathering asynchronous oblivious mobile robots in a ring.

[BibT_eX]

[DOI]

Euripides Markou

Andrzej Pelc

Theor. Comput. Sci., 2008

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

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2008

Approximation bounds for Black Hole Search problems.

[BibT_eX]

[DOI]

Networks, 2008

On k-connectivity problems with sharpened triangle inequality.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2008

Fast periodic graph exploration with constant memory.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 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

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

Improved Approximation Results for the Minimum Energy Broadcasting Problem.

[BibT_eX]

[DOI]

Algorithmica, 2007

On the Complexity of Distributed Greedy Coloring.

[BibT_eX]

[DOI]

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

Cost Minimisation in Multi-interface Networks.

[BibT_eX]

[DOI]

Proceedings of the Network Control and Optimization, 2007

2006

Hardness and Approximation of Gathering in Static Radio Networks.

[BibT_eX]

[DOI]

Parallel Process. Lett., 2006

Constructing Incremental Sequences in Graphs.

[BibT_eX]

[DOI]

Algorithmic Oper. Res., 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

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

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

On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 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

2003

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

[BibT_eX]

[DOI]

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

2002

Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 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

1998

Improved Compressions of Cube-Connected Cycles Networks.

[BibT_eX]

[DOI]

IEEE Trans. Parallel Distributed Syst., 1998

Effective Systolic Algorithms for Gossiping in Cycles.

[BibT_eX]

[DOI]

Parallel Process. Lett., 1998

Compressing cube-connected cycles and butterfly networks.

[BibT_eX]

[DOI]

Reinhard Lüling

Burkhard Monien

Networks, 1998

Optimal Embedding of Complete Binary Trees into Lines and Grids.

[BibT_eX]

[DOI]

J. Parallel Distributed Comput., 1998

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

[BibT_eX]

[DOI]

Discret. Appl. Math., 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

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

[BibT_eX]

[DOI]

Inf. Comput., 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

The Complexity of Systolic Dissemination of Information in Interconnection Networks.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 1994

Broadcasting in Butterfly and deBruijn Networks.

[BibT_eX]

[DOI]

Discret. Appl. Math., 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

1993

Gossiping in Vertex-Disjoint Path Mode in Interconnection Networks.

[BibT_eX]

[DOI]

Juraj Hromkovic