Titlebook: Computing and Combinatorics; 5th Annual Internati Takano Asano,Hideki Imai,Takeshi Tokuyama Conference proceedings 1999 Springer-Verlag Ber

POLYP

Conference proceedings 1999ial talk by Kurt Mehlhorn on LEDA (Library of E cient Data types and Algorithms). The Hao Wang Award (inaugurated at COCOON ’97) is given to honor the paper judged by the program committee to have the greatest scienti c merit. The recipients of the Hao Wang Award 1999 were Hiroshi Nagamochi and Tos-

钻孔

The Web as a Graph: Measurements, Models, and Methodsas several hundred million nodes today, over a billion links, and appears to grow exponentially with time. There are many reasons — mathematical, sociological, and commercial — for studying the evolution of this graph. In this paper we begin by describing two algorithms that operate on the Web graph

forestry

Some Observations on the Computational Complexity of Graph Accessibility Problem (Extended Abstract)roblem can be solved deterministically in space .(sw(.). log..), where . denotes the number of nodes and sw(.) denotes the separation-width of . that is an invariant of graphs introduced in this paper. We next observe that for the class of all graphs consisting of only two paths, the problem still r

glomeruli

An Approximation for Finding a Smallest 2-Edge-Connected Subgraph Containing a Specified Spanning Tre-connected spanning subgraph (.,.∪.) of . + . containing .. The problem, which is known to be NP-hard, admits a 2-approximation algorithm. However, obtaining a factor better than 2 for this problem has been one of the main open problems in the graph augmentation problem. In this paper, we present a

绝种

Theory of 2-3 Heapsdelete-min operations in .(. + . log .) time. The merit of the 2—3 heap is that it is conceptually simpler and easier to implement. The new data structure will have a wide application in graph algorithms.

运动吧

An External Memory Data Structure for Shortest Path Queries (Extended Abstract) trees in external memory so that bottom-up paths can be traversed I/O-efficiently, and we present I/O-efficient algorithms for tri-angulating planar graphs and computing small separators of such graphs. Using these techniques, we can construct a data structure that allows for answering shortest pat

JEER

Approximating the Nearest Neighbor Interchange Distance for Evolutionary Trees with Non-uniform Degrroblem of computing the nni distance has been studied over two decades (see e.g., [16,3,7,12,8,4]). The long-standing conjecture that the problem is NP-complete was proved only recently, whereas approximation algorithms for the problem have appeared in the literature for a while. Existing approximat