Wu Wen-tsun (auth.), Ding-Zhu Du, Xiang-Sun Zhang (eds.)3540583254, 9783540583257
The 79 papers accepted for inclusion in the volume after a careful reviewing process were selected from a total of almost 200 submissions. Besides many internationally renowned experts, a number of excellent Chinese researchers present their results to the international scientific community for the first time here. The volume covers all relevant theoretical and many applicational aspects of algorithms and computation.
Table of contents :
Polynomial equations-solving and its applications….Pages 1-9
Quasi-random combinatorial structures….Pages 10-10
Hamiltonian abstract Voronoi diagrams in linear time….Pages 11-19
Every set of disjoint line segments admits a binary tree….Pages 20-28
The traveling cameraman problem, with applications to automatic optical inspection….Pages 29-37
On determining the congruity of point sets in higher dimensions….Pages 38-46
On random hard sets for NP….Pages 47-55
Computing solutions uniquely collapses the polynomial hierarchy….Pages 56-64
Verifying the determinant in parallel….Pages 65-73
Hardness of approximating graph transformation problem….Pages 74-82
Randomized wait-free naming….Pages 83-91
Unifying themes for network selection….Pages 92-100
Robust asynchronous algorithms in networks with a fault detection ring….Pages 101-109
Distributed algorithms for finding small cycle covers in arbitrary networks….Pages 110-118
A neural network model for quadratic programming with simple upper and lower bounds and its application to linear programming….Pages 119-127
Analysis of the convergency of topology preserving neural networks on learning….Pages 128-136
On helping and interactive proof systems….Pages 137-145
Average time complexity of the SAT 1.2 algorithm….Pages 146-154
Average cost to produce partial orders….Pages 155-163
Two notes on low-density subset sum algorithm….Pages 164-171
Rotation distance, triangulations of planar surfaces and hyperbolic geometry….Pages 172-180
Finitely representable spatial objects and efficient computation….Pages 181-189
Computing all small cuts in undirected networks….Pages 190-198
Edge-coloring and f -coloring for various classes of graphs….Pages 199-207
Edge-disjoint paths in permutation graphs….Pages 208-216
Minimum augmentation to k -edge-connect specified vertices of a graph….Pages 217-225
Algorithmic Chernoff-Hoeffding inequalities in integer programming….Pages 226-233
Approximate pattern matching with samples….Pages 234-242
An efficient optimal algorithm for minimizing the overall communication cost in replicated data management….Pages 243-251
Multispace search: A new optimization approach….Pages 252-260
Realizing degree sequences in parallel….Pages 261-269
Efficient sequential and parallel algorithms for the negative cycle problem….Pages 270-278
Fast and efficient operations on Parallel Priority Queues….Pages 279-287
Heaps with bits….Pages 288-296
Components and projections of curves over finite fields….Pages 297-305
On the approximation of finding various minimal, maximal, and consistent sequences….Pages 306-314
A linear-time algorithm for computing characteristic strings….Pages 315-323
The maximum latency and identification of positive Boolean functions….Pages 324-332
Fast deterministic Hot-Potato routing on processor arrays….Pages 333-341
k -pairwise cluster fault tolerant routing in hypercubes….Pages 342-350
On Steiner minimal trees in grid graphs and its application to VLSI routing….Pages 351-359
Optimal routing of permutations on rings….Pages 360-368
Resource bounded randomness and weakly complete problems….Pages 369-377
Deterministic Ω automata vis-a-vis deterministic Buchi automata….Pages 378-386
Quantum computation and NP-complete problems….Pages 387-395
Separability and one-way functions….Pages 396-404
On the approximation of largest common subtrees and largest common point sets….Pages 405-413
An approximation scheme for some Steiner tree problems in the plane….Pages 414-422
A chain decomposition algorithm for the proof of a property on minimum weight triangulations….Pages 423-427
Generating algorithm for quasi-full Steiner tree….Pages 428-432
Analysing deletions in competitive self-adjusting linear list algorithms….Pages 433-441
Are Fibonacci heaps optimal?….Pages 442-450
Simple and efficient graph compression schemes for dense and complement graphs….Pages 451-459
Improved algorithms for coloring random graphs….Pages 460-468
On the parallel complexity of solving recurrence equations….Pages 469-477
Extended graph connectivity and its gradually increasing parallel complexity….Pages 478-486
Parallel h-v drawings of binary trees….Pages 487-495
An efficient parallel strategy for recognizing series-parallel graphs….Pages 496-504
Orthogonal queries in segments and triangles….Pages 505-513
Further computational geometry in secondary memory….Pages 514-522
Shortest safari routes in simple polygons….Pages 523-530
On greedy tetrahedralization of points in 3D….Pages 532-540
The totally-perfect bipartite graph and its construction….Pages 541-549
k Best Cuts for Circular-Arc graphs….Pages 550-558
Revisiting circular arc graphs….Pages 559-566
Weighted irredundance of interval graphs….Pages 567-574
A reordering operation for an ordered binary decision diagram and an extended framework for combinatorics of graphs….Pages 575-583
On the size of ordered binary decision diagrams representing threshold functions….Pages 584-592
Nonuniform lowness and strong nonuniform lowness….Pages 593-599
Definition and existence of super complexity cores….Pages 600-606
Efficient algorithms for assigning chain-like tasks on a chain-like network computer….Pages 607-615
Manpower scheduling with shift change constraints….Pages 616-624
Fast algorithms for transversal matroid intersection problems….Pages 625-633
A convex hull algorithm on coarse-grained multiprocessor….Pages 634-642
A multiway merging network….Pages 643-651
Reporting and counting intersections of lines within a polygon….Pages 652-659
A new problem in string searching….Pages 660-668
Achieving the shortest clock period by inserting the minimum amount of delay….Pages 669-677
A randomized algorithm to Finite Automata Public Key Cryptosystem….Pages 678-686
Reviews
There are no reviews yet.