15 citations · 45 across the 12 of their papers we have counts for
Showing 2009Show all
3 papers · 1 filter
math.CO2009★ 1 cited
Uniqueness of graph square roots of girth six
Anna Adamaszek, Michal Adamaszek
We prove that if two graphs of girth at least 6 have isomorphic squares, then the graphs themselves are isomorphic. This is the best possible extension of the results of Ross and H…
cs.DS2009
Large-girth roots of graphs
Anna Adamaszek, Michal Adamaszek
We study the problem of recognizing graph powers and computing roots of graphs. We provide a polynomial time recognition algorithm for r-th powers of graphs of girth at least 2r+3,…
cs.DS2009
PTAS for k-tour cover problem on the plane for moderately large values of k
Anna Adamaszek, Artur Czumaj, Andrzej Lingas
Let P be a set of n points in the Euclidean plane and let O be the origin point in the plane. In the k-tour cover problem (called frequently the capacitated vehicle routing problem…