225 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- Université Paris CitéFR306 papers
- Centre National de la Recherche ScientifiqueFR291 papers
- Université Paris DiderotFR88 papers
- Sorbonne Paris CitéFR62 papers
- Délégation Paris 7FR38 papers
- Institut national de recherche en sciences et technologies du numériqueFR35 papers
- Laboratoire Bordelais de Recherche en InformatiqueFR31 papers
- Sorbonne UniversitéFR31 papers
- Centre for Quantum TechnologiesSG23 papers
- Université Paris-SaclayFR22 papers
- National University of SingaporeSG21 papers
- LIP6FR20 papers
40 papers · 1 filter
Buy-at-Bulk Facility Location on Trees
Shamisa Nematollahi, Daniel Vaz
We consider the buy-at-bulk facility location problem (BBFL), a problem combining the classic facility location problem with buy-at-bulk network design, which finds motivation in t…
A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space
Benjamin Bergougnoux, Vera Chekan, Giannos Stamoulis
For a graph , the parameter treedepth measures the minimum depth among all forests , called elimination forests, such that is a subgraph of the ancestor-descendant closur…
Quasilinear-time eccentricities computation, and more, on median graphs
Pierre Bergé, Guillaume Ducoffe, Michel Habib
Computing the diameter, and more generally, all eccentricities of an undirected graph is an important problem in algorithmic graph theory and the challenge is to identify graph cla…
Canadian Traveller Problems in Temporal Graphs
Thomas Bellitto, Johanne Cohen, Bruno Escoffier +2
This paper formalises the Canadian Traveller problem as a positional two-player game on graphs. We consider two variants depending on whether an edge is blocked. In the locally-inf…
Practical Computation of Graph VC-Dimension
David Coudert, Mónika Csikós, Guillaume Ducoffe +1
For any set system , a subset is called \emph{shattered} if every results from the intersection of with some set in…
On computing approximate Lewis weights
Simon Apers, Sander Gribling, Aaron Sidford
In this note we provide and analyze a simple method that given an matrix, outputs approximate -Lewis weights, a natural measure of the importance of the rows w…
Holey graphs: very large Betti numbers are testable
Dániel Szabó, Simon Apers
We show that the graph property of having a (very) large -th Betti number for constant is testable with a constant number of queries in the dense graph model. More spe…
On the Length of Strongly Monotone Descending Chains over
Sylvain Schmitz, Lia Schütze
A recent breakthrough by Künnemann, Mazowiecki, Schütze, Sinclair-Banks, and Wegrzycki (ICALP, 2023) bounds the running time for the coverability problem in -dimensional vector…
Matroid-Constrained Vertex Cover
Chien-Chung Huang, François Sellier
In this paper, we introduce the problem of Matroid-Constrained Vertex Cover: given a graph with weights on the edges and a matroid imposed on the vertices, our problem is to choose…
A Note on the Complexity of Maximizing Temporal Reachability via Edge Temporalisation of Directed Graphs
Alkida Balliu, Filippo Brunelli, Pierluigi Crescenzi +2
A temporal graph is a graph in which edges are assigned a time label. Two nodes u and v of a temporal graph are connected one to the other if there exists a path from u to v with i…
Minimum-Cost Temporal Walks under Waiting-Time Constraints in Linear Time
Filippo Brunelli, Laurent Viennot
In a temporal graph, each edge is available at specific points in time. Such an availability point is often represented by a ''temporal edge'' that can be traversed from its tail o…
A (simple) classical algorithm for estimating Betti numbers
Simon Apers, Sander Gribling, Sayantan Sen +1
We describe a simple algorithm for estimating the -th normalized Betti number of a simplicial complex over elements using the path integral Monte Carlo method. For a general…
A Simple Algorithm for Graph Reconstruction
Claire Mathieu, Hang Zhou
How efficiently can we find an unknown graph using distance queries between its vertices? We assume that the unknown graph is connected, unweighted, and has bounded degree. The goa…
Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
Parinya Chalermsook, Matthias Kaul, Matthias Mnich +3
The fundamental sparsest cut problem takes as input a graph together with the edge costs and demands, and seeks a cut that minimizes the ratio between the costs and demands acr…
A PTAS for Capacitated Vehicle Routing on Trees
Claire Mathieu, Hang Zhou
We give a polynomial time approximation scheme (PTAS) for the unit demand capacitated vehicle routing problem (CVRP) on trees, for the entire range of the tour capacity. The result…
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet +6
A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textsc{Maximum Cliq…
Subquadratic-time algorithm for the diameter and all eccentricities on median graphs
Pierre Bergé, Guillaume Ducoffe, Michel Habib
On sparse graphs, Roditty and Williams [2013] proved that no -time algorithm achieves an approximation factor smaller than for the diameter prob…
Probabilistic Analysis of Euclidean Capacitated Vehicle Routing
Claire Mathieu, Hang Zhou
We give a probabilistic analysis of the unit-demand Euclidean capacitated vehicle routing problem in the random setting, where the input distribution consists of unit-demand cu…
Diameter, radius and all eccentricities in linear time for constant-dimension median graphs
Pierre Bergé, Michel Habib
Median graphs form the class of graphs which is the most studied in metric graph theory. Recently, Bénéteau et al. [2019] designed a linear-time algorithm computing both the -cl…
Decomposable Submodular Function Minimization via Maximum Flow
Kyriakos Axiotis, Adam Karczmarz, Anish Mukherjee +2
This paper bridges discrete and continuous optimization approaches for decomposable submodular function minimization, in both the standard and parametric settings. We provide impro…
On Computing Pareto Optimal Paths in Weighted Time-Dependent Networks
Filippo Brunelli, Pierluigi Crescenzi, Laurent Viennot
A weighted point-availability time-dependent network is a list of temporal edges, where each temporal edge has an appearing time value, a travel time value, and a cost value. In th…
Large Very Dense Subgraphs in a Stream of Edges
Claire Mathieu, Michel de Rougemont
We study the detection and the reconstruction of a large very dense subgraph in a social graph with nodes and edges given as a stream of edges, when the graph follows a pow…
Intermittent Inverse-Square Lévy Walks are Optimal for Finding Targets of All Sizes
Brieuc Guinard, Amos Korman
Lévy walks are random walk processes whose step-lengths follow a long-tailed power-law distribution. Due to their abundance as movement patterns of biological organisms, significan…
Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
Florent Foucaud, Hervé Hocquard, Dimitri Lajou +2
We study the complexity of graph modification problems with respect to homomorphism-based colouring properties of edge-coloured graphs. A homomorphism from edge-coloured graph …