1 citations · 1 across the 2 of their papers we have counts for
5 papers
Collective fast delivery by energy-efficient agents
Andreas Bärtschi, Daniel Graf, Matus Mihalak
We consider k mobile agents initially located at distinct nodes of an undirected graph (on n nodes, with edge lengths) that have to deliver a single item from a given source node s…
Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm
Annette M. C. Ficker, Thomas Erlebach, Matus Mihalak +1
Consider a problem where 4k given vectors need to be partitioned into k clusters of four vectors each. A cluster of four vectors is called a quad, and the cost of a quad is the sum…
Multicast Network Design Game on a Ring
Akaki Mamageishvili, Matus Mihalak
In this paper we study quality measures of different solution concepts for the multicast network design game on a ring topology. We recall from the literature a lower bound of 4/3…
Improving the H_k-Bound on the Price of Stability in Undirected Shapley Network Design Games
Yann Disser, Andreas Emil Feldmann, Max Klimm +1
In this paper we show that the price of stability of Shapley network design games on undirected graphs with k players is at most (k^3(k+1)/2-k^2) / (1+k^3(k+1)/2-k^2) H_k = (1 - Θ(…
Computing Minimum Spanning Trees with Uncertainty
Thomas Erlebach, Michael Hoffmann, Danny Krizanc +2
We consider the minimum spanning tree problem in a setting where information about the edge weights of the given graph is uncertain. Initially, for each edge of the graph only…