Robert Scheffler
YOU?
Author Swipe
View article: The Partial Search Order Problem
The Partial Search Order Problem Open
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 ordering…
View article: Sandwich Monotonicity and the Recognition of Weighted Graph Classes
Sandwich Monotonicity and the Recognition of Weighted Graph Classes Open
Edge-weighted graphs play an important role in the theory of Robinsonian matrices and similarity theory, particularly via the concept of level graphs, that is, graphs obtained from an edge-weighted graph by removing all sufficiently light …
View article: A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs
A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs Open
We consider the problem of finding a Hamiltonian path or a Hamiltonian cycle with precedence constraints in the form of a partial order on the vertex set. We show that the path problem is $\mathsf{NP}$-complete for graphs of pathwidth 4 wh…
View article: A Graph Width Perspective on Partially Ordered Hamiltonian Paths
A Graph Width Perspective on Partially Ordered Hamiltonian Paths Open
We consider the problem of finding a Hamiltonian path with precedence constraints in the form of a partial order on the vertex set. This problem is known as Partially Ordered Hamiltonian Path Problem (POHPP). Here, we study the complexity …
View article: Computing Hamiltonian Paths with Partial Order Restrictions
Computing Hamiltonian Paths with Partial Order Restrictions Open
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 …
View article: Computing Hamiltonian Paths with Partial Order Restrictions
Computing Hamiltonian Paths with Partial Order Restrictions Open
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 p…
View article: Recognizing LBFS trees of bipartite graphs
Recognizing LBFS trees of bipartite graphs Open
The graph searches Breadth First Search (BFS) and Depth First Search (DFS) and the spanning trees constructed by them are some of the most basic concepts in algorithmic graph theory. BFS trees are first-in trees, i.e., every vertex is conn…
View article: The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs
The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs Open
We propose a novel way of generalizing the class of interval graphs, via a graph width parameter called simultaneous interval number. This parameter is related to the simultaneous representation problem for interval graphs and defined as t…
View article: Graph Search Trees and the Intermezzo Problem
Graph Search Trees and the Intermezzo Problem Open
The last in-tree recognition problem asks whether a given spanning tree can be derived by connecting each vertex with its rightmost left neighbor of some search ordering. In this study, we demonstrate that the last-in-tree recognition prob…
View article: Graph Search Trees and Their Leaves
Graph Search Trees and Their Leaves Open
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 pa…
View article: Certifying Fully Dynamic Algorithms for Recognition and Hamiltonicity of Threshold and Chain Graphs
Certifying Fully Dynamic Algorithms for Recognition and Hamiltonicity of Threshold and Chain Graphs Open
Solving problems on graphs dynamically calls for algorithms to function under repeated modifications to the graph and to be more efficient than solving the problem for the whole graph from scratch after each modification. Dynamic algorithm…
View article: On the recognition of search trees generated by BFS and DFS
On the recognition of search trees generated by BFS and DFS Open
The spanning trees of a graph constructed by the graph searches BFS and DFS are some of the most elementary structures in algorithmic graph theory. BFS-trees are first-in trees, i.e., every vertex is connected to its first visited neighbor…
View article: Linearizing Partial Search Orders
Linearizing Partial Search Orders Open
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 ordering…
View article: The Distance Orientation Problem
The Distance Orientation Problem Open
The Distance Orientation Problem (DOP) is formulated as follows: Given a graph with positive weights on its edges, are there weights for the vertices, such that for every edge x y it holds that the absolute difference between the weights o…
View article: Linear Time LexDFS on Chordal Graphs.
Linear Time LexDFS on Chordal Graphs. Open
Lexicographic Depth First Search (LexDFS) is a special variant of a Depth First Search (DFS), which was introduced by Corneil and Krueger in 2008. While this search has been used in various applications, in contrast to other graph searches…
View article: Linear Time LexDFS on Chordal Graphs
Linear Time LexDFS on Chordal Graphs Open
Lexicographic Depth First Search (LexDFS) is a special variant of a Depth First Search (DFS), which was introduced by Corneil and Krueger in 2008. While this search has been used in various applications, in contrast to other graph searches…
View article: On the End-Vertex Problem of Graph Searches
On the End-Vertex Problem of Graph Searches Open
End vertices of graph searches can exhibit strong structural properties and are crucial for many graph algorithms. The problem of deciding whether a given vertex of a graph is an end-vertex of a particular search was first introduced by Co…
View article: Optimization and simulation of fixed-time traffic signal control in real-world applications
Optimization and simulation of fixed-time traffic signal control in real-world applications Open
This paper contributes to the question how to optimize fixed-time traffic signal coordinations for real-world applications. Therefore, two models are combined: An analytically model that optimizes fixed-time plans based on a cyclically tim…
View article: On the End-Vertex Problem of Graph Searches
On the End-Vertex Problem of Graph Searches Open
End vertices of graph searches can exhibit strong structural properties and are crucial for many graph algorithms. The problem of deciding whether a given vertex of a graph is an end-vertex of a particular search was first introduced by Co…
View article: Nash equilibria in routing games with edge priorities
Nash equilibria in routing games with edge priorities Open
In this paper we present a new competitive packet routing model with edge priorities. We consider players that route selfishly through a network over time and try to reach their destinations as fast as possible. If the number of players wh…
View article: Optimizing Traffic Signal Settings for Public Transport Priority
Optimizing Traffic Signal Settings for Public Transport Priority Open
In order to promote public transport many municipalities use traffic signal control with a priority for buses or trams. In this paper, we address the problem of finding optimal passive transit signal priority settings. Building on a cyclic…
View article: Optimizing Traffic Signal Timings for Mega Events
Optimizing Traffic Signal Timings for Mega Events Open
Most approaches for optimizing traffic signal timings deal with the daily traffic. However, there are a few occasional events like football matches or concerts of musicians that lead to exceptional traffic situations. Still, such events oc…