Feeds:
Posts
Comments

Archive for December, 2007

Bottleneck Spanning Tree

A MST is obviously a BST. In fact, a simply linear algorithm exists for BST.
It appears in CLRS problem  23-3, but I didn’t come up with it and just Google it. I stupid!!!
It looks like a divide and conquer algorithm.
Find the median of all edge weights Em.
Using a DFS to check whether there exists a spanning tree with edge  weights not greater than Em.
If yes, remove all edges of weight greater than Em. Repeat.
If no, contract  all edges  of weight not greater than Em and get a smaller graph. Repeat.

Obviously, each edge is processed one time. 
Advertisements

Read Full Post »

A segment tree T stores a set S of n intervals on the line. A standard segment tree is a balanced binary search tree over the 2n endpoints of S that are stored at the leavesof T . We use the same notation for both a leaf and the point that it contains. We associate an interval denoted
by range(v) with each node v in T . If v is a leaf then range(v) is the interval [v, v]. If v is an internal node, where w is the leftmost leaf in the subtree rooted by v, and z is the rightmost leaf in the subtree rooted by v, then range(v) = [w, z]. We associate with each node v in T a set S(v) consisting of all segments s in S containing range(v) but not containing range(p(v)). Each node v in T holds a secondary data structure, representing the set S(v).
An interval tree is defined similarly. The difference is that in an interval tree an interval s = (xs, xe) is in S(v) if and only if v is the lowest common ancestor of xs and xe in T . It follows that a segment tree required O(n log n) space and an interval tree requires O(n) space.
 

Read Full Post »

Sometime, we need maintain a segment tree, which supports querying a minimal of a specified interval and adding a constant to a specified interval. It’s a common problem in programming contest. Usually, we maintain the interval segment tree by a folk technique called "deferred operation" or "contract subtree". Let’s see how Tarjan dealt with this problem in his paper on Dynamic Tree.
Define
dvalue[v]=value[v]-value[parent[v]] if v is not root, otherwise value[v] if v is root.
dmin[v]=min[v]-min[parent[v]] if v is not root, otherwise min[v] if v is root.
It’s easy to maintain the segment tree of dvalue[] and dmin[].
Moreover, it’s elegant!  

Read Full Post »

How to solve a difference constraints system subjected to that a subset (not necessary all)
of unknowns must be integral? 

Read Full Post »