480 citations
- Data61AU6 papers
- University of Applied Sciences and Arts of Southern SwitzerlandCH5 papers
- Ghent UniversityBE3 papers
- Hokkaido UniversityJP2 papers
- Technical University of MunichDE2 papers
- ArcelorMittal (France)FR1 paper
- Case Western Reserve UniversityUS1 paper
- Centre National de la Recherche ScientifiqueFR1 paper
- École Nationale Supérieure des Mines de ParisFR1 paper
- Indian Institute of Technology GuwahatiIN1 paper
- InsermFR1 paper
- Institut CurieFR1 paper
4 papers · 1 filter
On Pairwise Spanners
Marek Cygan, Fabrizio Grandoni, Telikepalli Kavitha
Given an undirected -node unweighted graph , a spanner with stretch function is a subgraph such that, if two nodes are at distance in $…
LP Rounding for k-Centers with Non-uniform Hard Capacities
Marek Cygan, MohammadTaghi Hajiaghayi, Samir Khuller
In this paper we consider a generalization of the classical k-center problem with capacities. Our goal is to select k centers in a graph, and assign each node to a nearby center, s…
On Min-Power Steiner Tree
Fabrizio Grandoni
In the classical (min-cost) Steiner tree problem, we are given an edge-weighted undirected graph and a set of terminal nodes. The goal is to compute a min-cost tree S which spans a…
Deterministic parameterized connected vertex cover
Marek Cygan
In the Connected Vertex Cover problem we are given an undirected graph G together with an integer k and we are to find a subset of vertices X of size at most k, such that X contain…