Efficient approximation algorithms for shortest cycles in undirected graphs.

Andrzej Lingas Eva-Marta Lundell

Published in: Inf. Process. Lett. (2009)

Keyphrases

approximation algorithms
undirected graph
np hard
special case
disjoint paths
vertex cover
minimum cost
worst case
primal dual
approximation ratio
set cover
constant factor
randomized algorithms
open shop
shortest path
planar graphs
probability distribution