Uri Zwick, Michael S. Paterson (auth.), Ding-Zhu Du, Ming Li (eds.)354060216X, 9783540602163
The 52 thoroughly refereed full papers and the 22 short presentations included in this volume were selected from a total of 120 submissions. All current aspects of theoretical computer science and combinatorial mathematics related to computing are addressed; in particular, there are sections on complexity theory, graph drawing, computational geometry, databases, graph algorithms, distributed programming and logic, combinatorics, machine models, combinatorial designs, algorithmic learning, algorithms, distributed computing, and scheduling.
Table of contents :
The complexity of mean payoff games….Pages 1-10
Approximation of coNP sets by NP-complete sets….Pages 11-20
How to draw a planar clustered graph….Pages 21-30
An efficient orthogonal grid drawing algorithm for cubic graphs….Pages 31-40
Constrained independence system and triangulations of planar point sets….Pages 41-50
Three dimensional weak visibility: Complexity and applications….Pages 51-60
Rectangulating rectilinear polygons in parallel….Pages 61-70
Efficient randomized incremental algorithm for the closest pair problem using Leafary trees….Pages 71-80
Computing infinite relations using finite expressions: A new approach to the safety issue in relational databases….Pages 81-90
Set-term unification in a logic database language….Pages 91-100
Computations with finite closure systems and implications….Pages 101-110
Maximum tree-packing in time O (n 5/2 )….Pages 111-120
Optimal algorithms for finding connected components of an unknown graph….Pages 121-130
The multi-weighted spanning tree problem….Pages 131-140
Algorithmic graph embeddings….Pages 141-150
Analysis of quorum-based protocols for distributed (k+1)-exclusion….Pages 151-160
A highly fault-tolerant quorum consensus method for managing replicated data….Pages 161-170
Constructing Craig interpolation formulas….Pages 171-180
Currying of order-sorted term rewriting systems….Pages 181-190
Stack and queue number of 2-trees….Pages 191-202
Shortest paths in random weighted graphs….Pages 203-212
Simple reduction of f -colorings to edge-colorings….Pages 213-222
Output-size sensitiveness of OBDD construction through maximal independent set problem….Pages 223-228
Small weight bases for hamming codes….Pages 229-234
Toeplitz words, generalized periodicity and periodically iterated morphisms….Pages 235-243
A construction for enumerating k -coloured Motzkin paths….Pages 244-253
On public-key cryptosystem based on Church-Rosser string-rewriting systems….Pages 254-263
Extending the Hong-Kung model to memory hierarchies….Pages 264-269
On log-time alternating Turing machines of alternation depth k ….Pages 270-281
New bound for affine resolvable designs and its application to authentication codes….Pages 282-291
Dense packings of 3k(k+1)+1 equal disks in a circle for k = 1, 2, 3, 4, and 5….Pages 292-302
Efficient parallel algorithms for some tree layout problems….Pages 303-312
Conservative algorithms for parallel and sequential integer sorting….Pages 313-323
An optimal algorithm for proper learning of unions of two rectangles with queries….Pages 324-333
Disjunctions of negated counting functions are efficiently learnable with equivalence queries….Pages 334-343
Non-empty cross-3-intersection theorems of subsets….Pages 344-349
Convexity of minimal total dominating functions in graphs….Pages 350-356
Transformations for maximal planar graphs with minimum degree five….Pages 357-365
An asynchronous parallel method for linear systems….Pages 366-371
On a kind of sequence of polynomials….Pages 372-378
Hamiltonian cycles in 2-generated Cayley digraphs of abelian groups….Pages 379-383
Pandiagonal magic squares….Pages 384-387
PFFM and Quasi-Morishima matrices….Pages 388-391
Edge-face total chromatic number of outerplanar graphs with Δ (G)=6….Pages 392-395
Sets computable in polynomial time on average….Pages 396-399
Rankable distributions do not provide harder instances than uniform distributions….Pages 400-409
Transformations that preserve malignness of universal distributions….Pages 410-419
Intersection suffices for Boolean hierarchy equivalence….Pages 420-429
Searching rigid data structures….Pages 430-435
A better subgraph of the minimum weight triangulation….Pages 436-445
Sequence decomposition method for computing a Gröbner basis and its application to bivariate spline….Pages 446-451
A broadcasting algorithm on the arrangement graph….Pages 452-455
A fast maximum finding algorithm on broadcast communication….Pages 456-461
Broadcasting in general networks I: Trees….Pages 462-471
Uni-directional alternating group graphs….Pages 472-481
On separating proofs of knowledge from proofs of membership of languages and its application to secure identification schemes….Pages 482-489
Compact location problems with budget and communication constraints….Pages 490-495
Minimum dominating sets of intervals on lines….Pages 496-509
Two-dimensional pattern matching on a dynamic library of texts….Pages 510-519
Structure in approximation classes….Pages 520-529
Improved lower bounds for the randomized Boppana-Halldórsson algorithm for MAXCLIQUE….Pages 530-538
MNP: A class of NP optimization problems….Pages 539-548
Semidefinite programming and its applications to NP problems….Pages 549-558
Analysis and experimentation on list update algorithms….Pages 559-565
An exact branch and bound algorithm for the Steiner Problem in Graphs….Pages 566-575
A physical model for the satisfiability problem….Pages 576-581
An efficient algorithm for local testability problem of finite state automata….Pages 582-590
Scheduling task-tree with additive scales on parallel/distributed machines….Pages 591-596
Single-vehicle scheduling problem on a straight line with time window constraints….Pages 597-606
An on-line algorithm for some uniform processor Scheduling….Pages 607-616
An algebraic characterization of tractable constraints….Pages 617-626
Limit property of unbalanced development in economic network….Pages 627-632
Document processing, theory, and practice….Pages 633-642
Matching and comparing sequences in molecular biology….Pages 643-646
Primal-dual schema based approximation algorithms….Pages 647-647
….Pages 648-649
Reviews
There are no reviews yet.