25 citations · 40 across the 13 of their papers we have counts for
16 papers
Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs
Steven Chaplick, Martin Frohn, Steven Kelk +2
In this article we prove that the minimum-degree greedy algorithm, with adversarial tie-breaking, is a -approximation for the Maximum Independent Set problem on interval gra…
Relaxed Agreement Forests
Virginia Aardevol Martinez, Steven Chaplick, Steven Kelk +3
There are multiple factors which can cause the phylogenetic inference process to produce two or more conflicting hypotheses of the evolutionary history of a set X of biological ent…
Snakes and Ladders: a Treewidth Story
Steven Chaplick, Steven Kelk, Ruben Meuwese +2
Let be an undirected graph. We say that contains a ladder of length if the grid graph is an induced subgraph of that is only connected to the rest…
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…
Sequential Solutions in Machine Scheduling Games
Cong Chen, Paul Giessler, Akaki Mamageishvili +2
We consider the classical machine scheduling, where jobs need to be scheduled on machines, and where job scheduled on machine contributes to…
Collaborative Delivery with Energy-Constrained Mobile Robots
Andreas Bärtschi, Jérémie Chalopin, Shantanu Das +5
We consider the problem of collectively delivering some message from a specified source to a designated target location in a graph, using multiple mobile agents. Each agent has a l…
Bribeproof mechanisms for two-values domains
Matúš Mihalák, Paolo Penna, Peter Widmayer
Schummer (Journal of Economic Theory 2000) introduced the concept of bribeproof mechanism which, in a context where monetary transfer between agents is possible, requires that mani…
Prime Factorization of the Kirchhoff Polynomial: Compact Enumeration of Arborescences
Matúš Mihalák, Przemysław Uznański, Pencho Yordanov
We study the problem of enumerating all rooted directed spanning trees (arborescences) of a directed graph (digraph) of vertices. An arborescence consisting of ed…
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…
An Upper Bound on the Price of Stability of Undirected Network Design Games
Akaki Mamageishvili, Matúš Mihalák, Simone Montemezzani
In the network design game with players, every player chooses a path in an edge-weighted graph to connect her pair of terminals, sharing costs of the edges on her path with all…
Tree Nash Equilibria in the Network Creation Game
Akaki Mamageishvili, Matus Mihalak, Dominik Muller
In the network creation game with n vertices, every vertex (a player) buys a set of adjacent edges, each at a fixed amount α > 0. It has been conjectured that for α >= n, every Nas…
Counting approximately-shortest paths in directed acyclic graphs
Matúš Mihalák, Rastislav Šrámek, Peter Widmayer
Given a directed acyclic graph with positive edge-weights, two vertices s and t, and a threshold-weight L, we present a fully-polynomial time approximation-scheme for the problem o…
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 - Θ(…
Simple Agents Learn to Find Their Way: An Introduction on Mapping Polygons
Jérémie Chalopin, Shantanu Das, Yann Disser +2
This paper gives an introduction to the problem of mapping simple polygons with autonomous agents. We focus on minimalistic agents that move from vertex to vertex along straight li…
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…