66 citations · 323 across the 55 of their papers we have counts for
4 papers · 1 filter
On the approximability and exact algorithms for vector domination and related problems in graphs
Ferdinando Cicalese, Martin Milanic, Ugo Vaccaro
We consider two graph optimization problems called vector domination and total vector domination. In vector domination one seeks a small subset S of vertices of a graph such that a…
Shortest paths between shortest paths and independent sets
Marcin Kaminski, Paul Medvedev, Martin Milanic
We study problems of reconfiguration of shortest paths in graphs. We prove that the shortest reconfiguration sequence can be exponential in the size of the graph and that it is NP-…
Competitive Boolean Function Evaluation: Beyond Monotonicity, and the Symmetric Case
Ferdinando Cicalese, Travis Gagie, Eduardo Laber +1
We study the extremal competitive ratio of Boolean function evaluation. We provide the first non-trivial lower and upper bounds for classes of Boolean functions which are not inclu…
A note on dilation coefficient, plane-width, and resolution coefficient of graphs
Martin Milanic, Tomaz Pisanski, Arjana Zitnik
In this note we study and compare three graph invariants related to the 'compactness' of graph drawing in the plane: the dilation coefficient, defined as the smallest possible quot…