Nordic Journal of Computing Bibliography

D. Fernàndez-Baca, G. Slutzki, and D. Eppstein. Using Sparsification for Parametric Minimum Spanning Tree Problems. Nordic Journal of Computing, 3(4):352-366, Winter 1996.

Two applications of sparsification to parametric computing are given. The first is a fast algorithm for enumerating all distinct minimum spanning trees in a graph whose edge weights vary linearly with a parameter. The second is an asymptotically optimal algorithm for the minimum ratio spanning tree problem, as well as other search problems, on dense graphs.

Categories and Subject Descriptors:

Additional Key Words and Phrases: algorithms, graphs, minimum ratio optimization, minimum spanning trees, parametric problems, sparsification

Selected papers that cite this one

Selected references


  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database