16 citations · 23 across the 7 of their papers we have counts for
4 papers · 1 filter
1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two
Piotr Berman, Marek Karpinski, Alex Zelikovsky
We give a 1.25 approximation algorithm for the Steiner Tree Problem with distances one and two, improving on the best known bound for that problem.
Approximating Transitivity in Directed Networks
Piotr Berman, Bhaskar DasGupta, Marek Karpinski
We study the problem of computing a minimum equivalent digraph (also known as the problem of computing a strong transitive reduction) and its maximum objective function variant, wi…
The Mixing Time of Glauber Dynamics for Colouring Regular Trees
Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski
We consider Metropolis Glauber dynamics for sampling proper -colourings of the -vertex complete -ary tree when . We give both upper and lower bounds…
Schemes for Deterministic Polynomial Factoring
Gábor Ivanyos, Marek Karpinski, Nitin Saxena
In this work we relate the deterministic complexity of factoring polynomials (over finite fields) to certain combinatorial objects we call m-schemes. We extend the known conditiona…