Titlebook: Algorithm Theory - SWAT 2000; 7th Scandinavian Wor Magnus M. Halldorsson Conference proceedings 2000 Springer-Verlag Berlin Heidelberg 2000

Incise

放气

装饰

Demokratie im postkommunistischen EU-RaumWe show how to maintain centers and medians for a collection of dynamic trees where edges may be inserted and deleted and node and edge weights may be changed. All updates are supported in O(log n) time, where . is the size of the tree(s) involved in the update.

上坡

Abrupt

Maintaining Center and Median in Dynamic TreesWe show how to maintain centers and medians for a collection of dynamic trees where edges may be inserted and deleted and node and edge weights may be changed. All updates are supported in O(log n) time, where . is the size of the tree(s) involved in the update.

收集

A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free GraphsIn this paper we consider the following problem. Given is a d-claw free graph G = (V,E,w) where w: V → R.. Our algorithm finds an independent set A such that w(A*)/w(A)≤ d/2 where A* is an independent that maximizes w(A*). The previous best polynomial time approximation algorithm obtained w(A*)/w(A)≤ 2d/3.

CAB

Dynamic Graph Algorithms with Applicationsgeneral edge connectivity within a factor .. Finally, on the more practical side, we will discuss how output sensitive algorithms for dynamic shortest paths have been applied successfully to speed up local search algorithms for improving routing on the internet, roughly doubling the capacity.

低能儿

Misgiving

Recognizing Weakly Triangulated Graphs by Edge Separabilityerization of weakly triangulated graphs, as well as a new recognition algorithm which, unlike the previous ones, is not based on the notion of 2-pair, but rather on the structural properties of the minimal separators of the graph. It also gives the strongest relationship to the class of triangulated graphs that has been established so far.

值得赞赏