TY - GEN A1 - Jahnke, Sonja A1 - Cruysen, Caren A1 - Prill, Robert A1 - Kittmann, Fabian A1 - Pflug, Nicola A1 - Albert, Justin Amadeus A1 - Camargo, Tibor de A1 - Arnrich, Bert A1 - Krolikowska, Aleksandra A1 - Kolcz, Anna A1 - Reichert, Pawel A1 - Oleksy, Lukasz A1 - Michel, Sven A1 - Kopf, Sebastian A1 - Wagner, Michael A1 - Scheffler, Sven A1 - Becker, Roland T1 - Protocol for a Randomized Crossover Trial to Evaluate the Effect of Soft Brace and Rigid Orthosis on Performance and Readiness to Return to Sport Six Months Post‑ACL‑Reconstruction T2 - Healthcare N2 - A randomized crossover trial was designed to investigate the influence of muscle activation and strength on functional stability/control of the knee joint, to determine whether bilateral imbalances still occur six months after successful anterior cruciate ligament reconstruction (ACLR), and to analyze whether the use of orthotic devices changes the activity onset of these muscles. Furthermore, conclusions on the feedforward and feedback mechanisms are highlighted. Therefore, twenty‑eight patients will take part in a modified Back in Action (BIA) test battery at an average of six months after a primary unilateral ACLR, which used an autologous ipsilateral semitendinosus tendon graft. This includes double‑leg and single‑leg stability tests, double‑leg and single‑leg countermovement jumps, double‑leg and single‑leg drop jumps, a speedy jump test, and a quick feet test. During the tests, gluteus medius and semitendinosus muscle activity are analyzed using surface electromyography (sEMG). Motion analysis is conducted using Microsoft Azure DK and 3D force plates. The tests are performed while wearing knee rigid orthosis, soft brace, and with no aid, in random order. Additionally, the range of hip and knee motion and hip abductor muscle strength under isometric conditions are measured. Furthermore, patient‑rated outcomes will be assessed. Y1 - 2023 U6 - https://doi.org/10.3390/healthcare11040513 SN - 2227-9032 VL - 11 IS - 4 ER - TY - GEN A1 - Köhler, Ekkehard A1 - Rogge, Markus A1 - Scheffler, Robert A1 - Strehler, Martin T1 - Optimal Bicycle Routes with Few Signal Stops T2 - 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023) Y1 - 2023 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2023.1 SN - 978-3-95977-302-7 VL - OASIcs - Open Access Series in Informatics; Band 115 SP - 1:1 EP - 1:14 PB - Schloss Dagstuhl – Leibniz-Zentrum für Informatik CY - Dagstuhl ER - TY - GEN A1 - Scheffler, Robert T1 - Graph Search Trees and Their Leaves T2 - Graph-Theoretic Concepts in Computer Science - 49th International Workshop, WG 2023, Fribourg, Switzerland, June 28–30, 2023 Y1 - 2023 SN - 978-3-031-43379-5 SN - 978-3-031-43380-1 U6 - https://doi.org/10.1007/978-3-031-43380-1_33 SP - 462 EP - 476 PB - Springer CY - Cham ER - TY - GEN A1 - Beisegel, Jesse A1 - Chiarelli, Nina A1 - Köhler, Ekkehard A1 - Milanič, Martin A1 - Muršič, Peter A1 - Scheffler, Robert T1 - The simultaneous interval number: a new width parameter that measures the similarity to interval graphs T2 - 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) Y1 - 2024 SN - 978-3-95977-318-8 U6 - https://doi.org/10.4230/LIPIcs.SWAT.2024.7 SP - 7:1 EP - 7:20 PB - Schloss Dagstuhl – Leibniz-Zentrum für Informatik CY - Dagstuhl ER - TY - GEN A1 - Beisegel, Jesse A1 - Köhler, Ekkehard A1 - Ratajczak, Fabienne A1 - Scheffler, Robert A1 - Strehler, Martin ED - Královič, Rastislav ED - Kučera, Antonín T1 - Graph search trees and the intermezzo problem T2 - 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) Y1 - 2024 SN - 978-3-95977-335-5 U6 - https://doi.org/10.4230/LIPICS.MFCS.2024.22 SP - 22:1 EP - 22:18 PB - Schloss Dagstuhl – Leibniz-Zentrum für Informatik CY - Dagstuhl ER - TY - GEN A1 - Scheffler, Robert T1 - Semi-proper interval graphs T2 - Discrete Applied Mathematics Y1 - 2025 U6 - https://doi.org/10.1016/j.dam.2024.08.016 SN - 0166-218X VL - 360 SP - 22 EP - 41 ER - TY - GEN A1 - Beisegel, Jesse A1 - Ratajczak, Fabienne A1 - Scheffler, Robert T1 - Computing hamiltonian paths with partial order restrictions T2 - ACM Transactions on Computation Theory N2 - When solving the Hamiltonian path problem it seems natural to be given additional precedence constraints for the order in which the vertices are visited. For example, one could decide whether a Hamiltonian path exists for a fixed starting point, or that some vertices are visited before another vertex. We consider the problem of finding a Hamiltonian path that observes all precedence constraints given in a partial order on the vertex set. We show that this problem is NP-complete even if restricted to complete bipartite graphs and posets of height 2. In contrast, for posets of width k there is a known O(k^2 n^k) algorithm for arbitrary graphs with n vertices. We show that it is unlikely that the running time of this algorithm can be improved significantly, i.e., there is no f(k) n^o(k) time algorithm under the assumption of the Exponential Time Hypothesis. Furthermore, for the class of outerplanar graphs, we give an O(n^2) algorithm for arbitrary posets. KW - Hamiltonian path KW - Partial order KW - Outerplanar graph KW - Partial search order KW - TSP-PC KW - Parameterized complexity Y1 - 2025 UR - https://dl.acm.org/doi/10.1145/3711844 U6 - https://doi.org/10.1145/3711844 SN - 1942-3454 VL - 17 IS - 1 SP - 1 EP - 24 ER - TY - GEN A1 - Beisegel, Jesse A1 - Köhler, Ekkehard A1 - Scheffler, Robert A1 - Strehler, Martin T1 - Certifying fully dynamic algorithms for recognition and Hamiltonicity of Threshold and Chain Graphs T2 - Algorithmica Y1 - 2023 U6 - https://doi.org/10.1007/s00453-023-01107-1 SN - 0178-4617 VL - 85 IS - 8 SP - 2454 EP - 2481 ER - TY - GEN A1 - Scheffler, Robert A1 - Strehler, Martin A1 - Vargas Koch, Laura T1 - Routing Games with Edge Priorities T2 - ACM Transactions on Economics and Computation Y1 - 2022 U6 - https://doi.org/10.1145/3488268 SN - 2167-8375 VL - 10 IS - 1 SP - 1:1 EP - 1:27 ER - TY - GEN A1 - Scheffler, Robert T1 - The partial search order problem T2 - The electronic journal of combinatorics N2 - In recent years, questions about the construction of special orderings of a given graph search were studied by several authors. On the one hand, the so called end-vertex problem introduced by Corneil et al. in 2010 asks for search orderings ending in a particular vertex. On the other hand, the problem of finding orderings that induce a given search tree was introduced already in the 1980s by Hagerup and received new attention most recently. Here, we consider a generalization of some of these problems by studying the question whether there is a search ordering that is a linear extension of a given partial order on a graph's vertex set. We show that this problem can be solved in polynomial time for Generic Search on general graphs as well as for searches called forgetful and partial orders of bounded width. Furthermore, we present polynomial-time algorithms on the classes of chordal bipartite graphs and split graphs for some searches including (Lexicographic) Breadth First Search. These algorithms generalize known algorithmic results for the End-Vertex Problem and the Search Tree Recognition Problem. Y1 - 2025 U6 - https://doi.org/10.37236/12654 SN - 1077-8926 VL - 32 IS - 4 SP - 1 EP - 37 ER - TY - GEN A1 - Scheffler, Robert T1 - On the leaves of graph search trees T2 - Ars Mathematica Contemporanea N2 - Graph searches and their respective search trees are widely used in algorithmic graph theory. The problem whether a given spanning tree can be a graph search tree has been considered for different searches, graph classes and search tree paradigms. Similarly, the question whether a particular vertex can be visited last by some search has been studied extensively in recent years. We combine these two problems by considering the question whether a vertex can be a leaf of a graph search tree. We show that for particular search trees, including DFS trees, this problem is easy if we allow the leaf to be the first vertex of the search ordering. We contrast this result by showing that the problem becomes hard for many searches, including DFS and BFS, if we forbid the leaf to be the first vertex. Additionally, we present several structural and algorithmic results for search tree leaves of chordal graphs. KW - Graph search KW - Graph search trees KW - Leaves KW - Chordal graphs Y1 - 2025 U6 - https://doi.org/10.26493/1855-3974.3238.2a8 SN - 1855-3974 VL - 26 IS - 1 SP - 1 EP - 29 PB - University of Primorska Press CY - Koper ER - TY - GEN A1 - Beisegel, Jesse A1 - Klost, Katharina A1 - Knorr, Kristin A1 - Ratajczak, Fabienne A1 - Scheffler, Robert ED - Agrawal, Akanksha ED - van Leeuwen, Erik Jan T1 - A graph width perspective on partially ordered Hamiltonian paths and cycles II : vertex and edge deletion numbers T2 - 20th International Symposium on Parameterized and Exact Computation (IPEC 2025) N2 - We consider the problem of finding a Hamiltonian path or cycle with precedence constraints in the form of a partial order on the vertex set. We study the complexity for graph width parameters for which the ordinary problems Hamiltonian Path and Hamiltonian Cycle are in FPT. In particular, we focus on parameters that describe how many vertices and edges have to be deleted to become a member of a certain graph class. We show that the problems are W[1]-hard for such restricted cases as vertex distance to path and vertex distance to clique. We complement these results by showing that the problems can be solved in XP time for vertex distance to outerplanar and vertex distance to block. Furthermore, we present some FPT algorithms, e.g., for edge distance to block. Additionally, we prove para-NP-hardness when considered with the edge clique cover number. KW - Hamiltonian path KW - Hamiltonian cycle KW - partial order KW - graph width parameter KW - parameterized complexity Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0030-drops-251623 UR - https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.30 SN - 978-3-95977-407-9 SP - 30:1 EP - 30:19 PB - Schloss Dagstuhl – Leibniz-Zentrum für Informatik CY - Wadern ER -