98 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- University of BucharestRO15 papers
- Institut de Recherche en Informatique FondamentaleFR5 papers
- Kent State UniversityUS5 papers
- Université Paris CitéFR4 papers
- Département d'InformatiqueFR3 papers
- École Normale Supérieure - PSLFR3 papers
- Universitatea Națională de Știință și Tehnologie Politehnica BucureștiRO3 papers
- Telecom Italia LabIT2 papers
- Aix-Marseille UniversitéFR1 paper
- Argosy UniversityUS1 paper
- Beijing Institute for Brain DisordersCN1 paper
- Bucharest Emergency University Hospital1 paper
9 papers · 1 filter
Faster approximation algorithms for computing shortest cycles on weighted graphs
Guillaume Ducoffe
Given an -vertex -edge graph with non negative edge-weights, the girth of is the weight of a shortest cycle in . For any graph with polynomially bounded intege…
Complexity of Computing the Anti-Ramsey Numbers for Paths
Saeed Akhoondian Amiri, Alexandru Popa, Mohammad Roghani +3
The anti-Ramsey numbers are a fundamental notion in graph theory, introduced in 1978, by Erd\" os, Simonovits and S\' os. For given graphs and the \emph{anti-Ramsey number}…
Polynomial-time Recognition of 4-Steiner Powers
Guillaume Ducoffe
The -power of a given graph is obtained from by adding an edge between every two distinct vertices at a distance at most in . We call a -Steiner…
An output-sensitive algorithm for the minimization of 2-dimensional String Covers
Alexandru Popa, Andrei Tanasescu
String covers are a powerful tool for analyzing the quasi-periodicity of 1-dimensional data and find applications in automata theory, computational biology, coding and the analysis…
The use of a pruned modular decomposition for Maximum Matching algorithms on some graph classes
Guillaume Ducoffe, Alexandru Popa
We address the following general question: given a graph class C on which we can solve Maximum Matching in (quasi) linear time, does the same hold true for the class of graphs that…
A quasi linear-time b-Matching algorithm on distance-hereditary graphs and bounded split-width graphs
Guillaume Ducoffe, Alexandru Popa
We present a quasi linear-time algorithm for Maximum Matching on distance-hereditary graphs and some of their generalizations. This improves on [Dragan, WG'97], who proposed such a…
Fast approximation and exact computation of negative curvature parameters of graphs
Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan +3
In this paper, we study Gromov hyperbolicity and related parameters, that represent how close (locally) a metric space is to a tree from a metric point of view. The study of Gromov…
Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and all Eccentricities in Graphs
Feodor F. Dragan, Guillaume Ducoffe, Michel Habib +1
In the context of fine-grained complexity, we investigate the notion of certificate enabling faster polynomial-time algorithms. We specifically target radius (minimum eccentricity)…
Heuristic algorithms for the min-max edge 2-coloring problem
Radu Stefan Mincu, Alexandru Popa
In multi-channel Wireless Mesh Networks (WMN), each node is able to use multiple non-overlapping frequency channels. Raniwala et al. (MC2R 2004, INFOCOM 2005) propose and study sev…