RK
Ralf Klasing
cs.DScs.DMmath.COcs.DCcs.ETcs.NIDifferent speedsGroup searchLinear searchMobile robots
On Valency
published · living versionsW_dqvfa3vp·v1 · currentpublished
Recognizing Label-Connected Graphs
with George B. Mertzios, Hendrik Molter, Nils Morawietz, Paul G. Spirakis
1 version
W_hqx4g89f·v1published
W_xsznprxh·v2published
Preprints & journals
24 papers in the corpus · 2009–2026Polynomial pathwidth for graphs vertex-coverable by few shortest paths and algorithms for quasi-shortest path covers2610.30458v1 · Li-Hsuan Chen, Florent Foucaud, Ling-Ju Hung et al.2026 · 0 citationsarXivon Valency
A Reusable Framework for Robust Approximation Algorithms in the Interval Uncertainty Model2609.11621v2 · Ralf Klasing, Tobias Momke, 'Emile Naquin2026 · 0 citationsarXivon Valency
The -good-neighbor diagnosability of product networks under the PMC model2503.19463v1 · Zhao Wang, Yaping Mao, Sun-Yuan Hsieh et al.2025 · 4 citationsarXiv
Graph Exploration with Edge Weight Estimates2501.18496v1 · Matthias Gehnen, Ralf Klasing, 'Emile Naquin2025 · 0 citationsarXiv
Greediness is not always a vice: Efficient Discovery Algorithms for Assignment Problems2410.09434v1 · Romaric Duvignau, Noel Gillet, Ralf Klasing2024 · 5 citationsarXiv
Online Unbounded Knapsack2407.02045v2 · Hans-Joachim Bockenhauer, Matthias Gehnen, Juraj Hromkovic et al.2024 · 0 citationsarXiv
Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?2403.04589v1 · Dibyayan Chakraborty, Antoine Dailly, Florent Foucaud et al.2024 · 0 citationsarXiv
Constructing disjoint Steiner trees in Sierpiński graphs2310.16463v3 · Chenxu Yang, Ping Li, Yaping Mao et al.2023 · 0 citationsFundamenta Informaticae, Volume 194, Issue 1 (July 5, 2025) fi:12478
Ramsey Achievement Games on Graphs : Algorithms and Bounds2303.04152v1 · Xiumin Wang, Zhong Huang, Xiangqian Zhou et al.2023 · 0 citationsarXiv
Perturbation results for distance-edge-monitoring numbers2301.02507v4 · Chenxu Yang, Ralf Klasing, Changxiang He et al.2023 · 5 citationsFundamenta Informaticae, Volume 191, Issue 2 (July 8, 2024) fi:10788
Monitoring the edges of product networks using distances2211.10743v2 · Wen Li, Ralf Klasing, Yaping Mao et al.2022 · 5 citationsJ. Comput. System Sci. 148 (2025), Paper No. 103602, 12 pp
The RED-BLUE SEPARATION problem on graphs2211.08283v1 · Subhadeep Ranjan Dev, Sanjana Dey, Florent Foucaud et al.2022 · 3 citationsTheoretical Computer Science 970:114061, 2023
On the distance-edge-monitoring numbers of graphs2211.04920v1 · Chengxu Yang, Ralf Klasing, Yaping Mao et al.2022 · 23 citationsarXiv
Perpetual maintenance of machines with different urgency requirements2202.01567v3 · Leszek Gasieniec, Tomasz Jurdzi'nski, Ralf Klasing et al.2022 · 10 citationsarXiv
Selected Papers of the 31st International Workshop on Combinatorial Algorithms, IWOCA 2020.36089986 · Gąsieniec, Leszek, Klasing, Ralf, Radzik, Tomasz2022 · 0 citationsAlgorithmica. 2022;84(10):3103-3106
Geographical Peer Matching for P2P Energy Sharing2112.11286v2 · Romaric Duvignau, Vincenzo Gulisano, Marina Papatriantafilou et al.2021 · 4 citationsarXiv
Monitoring the edges of a graph using distances2011.00029v2 · Florent Foucaud, Shih-Shun Kao, Ralf Klasing et al.2020 · 41 citationsDiscrete Applied Mathematics 319:424-438, 2022
Linear Search by a Pair of Distinct-Speed Robots.30872882 · Bampas, Evangelos, Czyzowicz, Jurek, Gąsieniec, Leszek et al.2020 · 21 citationsAlgorithmica. 2019;81(1):317-342
Parameterized and approximation complexity of the detection pair problem in graphs1601.05003v2 · Florent Foucaud, Ralf Klasing2016 · 0 citationsJournal of Graph Algorithms and Applications 21(6):1039-1056, 2017
Efficiently Testing T-Interval Connectivity in Dynamic Graphs1502.00089v3 · Arnaud Casteigts, Ralf Klasing, Yessin M. Neggaz et al.2015 · 12 citationsarXiv
Rendezvous of Heterogeneous Mobile Agents in Edge-weighted Networks1406.2008v1 · Dariusz Dereniowski, Ralf Klasing, Adrian Kosowski et al.2014 · 9 citationsarXiv
Improved Analysis of Deterministic Load-Balancing Schemes1404.4344v4 · Petra Berenbrink (SFU.ca), Ralf Klasing, Adrian Kosowski et al.2014 · 16 citationsarXiv
On the size of identifying codes in triangle-free graphs1010.5975v3 · Florent Foucaud, Ralf Klasing, Adrian Kosowski et al.2010 · 23 citationsDiscrete Applied Mathematics 160, 10-11 (2012) 1532-1546
More efficient periodic traversal in anonymous undirected graphs0905.1737v1 · J. Czyzowicz, S. Dobrev, L. Gasieniec et al.2009 · 11 citationsarXiv
Career total: 245 works. 24 are in this corpus.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.