Publication

Parametric and kinetic minimum spanning trees

Monika Henzinger
1998
Conference paper
Abstract

We consider the parametric minimum spanning tree problem, in which we are given a graph with edge weights that are linear functions of a parameter, and wish to computethe sequence of minimum spanning trees generated as, varies. We also consider the kinetic minimum spanning tree problem, in which, represents time and the graph is subject in addition to changes such as edge insertions, deletions, and modifications of the weight functions as time progresses. We solve both problems in time O(n.pow2(2/3).log(4/3).n) per combinatorial change in the tree (or randomized O(n.pow2(2/3).log(n)) per change). Our time bounds reduce to O(n.pow2(1/2).log(3/2).n) per change (O(n.pow2(1/2).log(n)) randomized) for planar graphs or other minor-closed families of graphs, and O(n.pow2(1/4).log(3/2).n) per change (O(n.pow2(1/4).log(n) randomized) for planar graphs with weight changes but no insertions or deletions.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.