23 citations · 66 across the 21 of their papers we have counts for
29 papers
Online and Incremental Fractional Vertex Cover on Trees
Júlia Baligács, Bartłomiej Bosek, Yann Disser +5
In this paper we study the fractional vertex cover problem on trees in two related models: online and incremental. In the online model, the vertices of the tree are known a priori…
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…
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…
A -Approximation for Tricolored Non-crossing Euclidean TSP
Júlia Baligács, Yann Disser, Andreas Emil Feldmann +1
In the Tricolored Euclidean Traveling Salesperson problem, we are given~ sets of points in the plane and are looking for disjoint tours, each covering one of the sets. Arora (…