5 papers
Highway Dimension: a Metric View
Andreas Emil Feldmann, Arnold Filtser
Realistic metric spaces (such as road/transportation networks) tend to be much more algorithmically tractable than general metrics. In an attempt to formalize this intuition, Abrah…
Generalized -Center: Distinguishing Doubling and Highway Dimension
Andreas Emil Feldmann, Tung Anh Vu
We consider generalizations of the -Center problem in graphs of low doubling and highway dimension. For the Capacitated -Supplier with Outliers (CkSwO) problem, we show an ef…
On Computational Aspects of Cores of Ordered Graphs
Michal ÄertÃk, Andreas Emil Feldmann, Jaroslav NeÅ¡etÅil +1
An ordered graph is a graph enhanced with a linear order on the vertex set. An ordered graph is a core if it does not have an order-preserving homomorphism to a proper subgraph. We…
On Computational Aspects of Ordered Matching Problems
Michal ÄertÃk, Andreas Emil Feldmann, Jaroslav NeÅ¡etÅil +1
Ordered matchings, defined as graphs with linearly ordered vertices, where each vertex is connected to exactly one edge, play a crucial role in the area of ordered graphs and their…
Complexity Aspects of Homomorphisms of Ordered Graphs
Michal ÄertÃk, Andreas Emil Feldmann, Jaroslav NeÅ¡etÅil +1
We examine ordered graphs, defined as graphs with linearly ordered vertices, from the perspective of homomorphisms (and colorings) and their complexities. We demonstrate the corres…