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

Capitulate

Area Minimization for Grid Visibility Representation of Hierarchically Planar Graphs we provide a quadratic algorithm that minimizes the drawing area with respect to a fixed planar embedding. This implies that the area minimization problem is polynomial time solvable restricted to the class of graphs whose planar embeddings are unique. Secondly, we show that the area minimization problem is generally NP-hard.

HEPA-filter

CRAB

A Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts in Graphsat runs in . time, where .(.,.) and ..(.,.) denote respectively the time bounds required to solve the maximum flow problem and the minimum 2-way cut problem in .. The bounds . for . = 5 and . for . = 6 improve the previous best randomized bounds . and ., respectively.

有危险

Die thermische Zustandsgleichung, some distance functional computes a best swap edge for every edge in .(.). We show that there exist fast swap algorithms (much faster than recomputing from scratch a new SPT) which also preserve the functionality of the affected SPT.

绕着哥哥问

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.

SYN

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 path queries on a planar graph I/O-efficiently.

Synthesize

A New Transference Theorem in the Geometry of Numbersgth of generating vectors of its dual. It generalizes the transference theorem due to Banaszczyk. The theorem is motivated by our efforts to improve Ajtai‘s connection factors in the connection of average-case to worst-case complexity of the shortest lattice vector problem. Our proofs are non-constructive, based on methods from harmonic analysis.

palette

On Bounds for the ,-Partitioning of Graphs such a cut for a given graph. For this we introduce a new lower bound method which is based on the solution of an extremal set problem and present bounds for some graph classes based on Hamming graphs.

Omniscient

不规则的跳动