Computing and Combinatorics

Inhaltsverzeichnis

The complexity of mean payoff games.- Approximation of coNP sets by NP-complete sets.- How to draw a planar clustered graph.- An efficient orthogonal grid drawing algorithm for cubic graphs.- Constrained independence system and triangulations of planar point sets.- Three dimensional weak visibility: Complexity and applications.- Rectangulating rectilinear polygons in parallel.- Efficient randomized incremental algorithm for the closest pair problem using Leafary trees.- Testing containment of object-oriented conjunctive queries is ? 2 p -hard.- Computing infinite relations using finite expressions: A new approach to the safety issue in relational databases.- Set-term unification in a logic database language.- Computations with finite closure systems and implications.- Maximum tree-packing in time O(n5/2).- Optimal algorithms for finding connected components of an unknown graph.- The multi-weighted spanning tree problem.- Algorithmic graph embeddings.- Analysis of quorum-based protocols for distributed (k+1)-exclusion.- A highly fault-tolerant quorum consensus method for managing replicated data.- Constructing Craig interpolation formulas.- Currying of order-sorted term rewriting systems.- Stack and queue number of 2-trees.- Shortest paths in random weighted graphs.- Simple reduction of f-colorings to edge-colorings.- Output-size sensitiveness of OBDD construction through maximal independent set problem.- Small weight bases for hamming codes.- Toeplitz words, generalized periodicity and periodically iterated morphisms.- A construction for enumerating k-coloured Motzkin paths.- On public-key cryptosystem based on Church-Rosser string-rewriting systems.- Extending the Hong-Kung model to memory hierarchies.- On log-time alternating Turing machines of alternation depth k.- New bound for affine resolvable designs and its application to authentication codes.- Dense packings of 3k(k+1)+1 equal disks in a circle for k = 1, 2, 3, 4, and 5.- Efficient parallel algorithms for some tree layout problems.- Conservative algorithms for parallel and sequential integer sorting.- An optimal algorithm for proper learning of unions of two rectangles with queries.- Disjunctions of negated counting functions are efficiently learnable with equivalence queries.- Non-empty cross-3-intersection theorems of subsets.- Convexity of minimal total dominating functions in graphs.- Transformations for maximal planar graphs with minimum degree five.- An asynchronous parallel method for linear systems.- On a kind of sequence of polynomials.- Hamiltonian cycles in 2-generated Cayley digraphs of abelian groups.- Pandiagonal magic squares.- PFFM and Quasi-Morishima matrices.- Edge-face total chromatic number of outerplanar graphs with ? (G)=6.- Sets computable in polynomial time on average.- Rankable distributions do not provide harder instances than uniform distributions.- Transformations that preserve malignness of universal distributions.- Intersection suffices for Boolean hierarchy equivalence.- A 2 3 log 3-competitive algorithm for the counterfeit coin problem.- Searching rigid data structures.- A better subgraph of the minimum weight triangulation.- Sequence decomposition method for computing a Gröbner basis and its application to bivariate spline.- A broadcasting algorithm on the arrangement graph.- A fast maximum finding algorithm on broadcast communication.- Broadcasting in general networks I: Trees.- Uni-directional alternating group graphs.- On separating proofs of knowledge from proofs of membership of languages and its application to secure identification schemes.- Compact location problems with budget and communication constraints.- Minimum dominating sets of intervals on lines.- Two-dimensional pattern matching on a dynamic library of texts.- Structure in approximation classes.- Improved lower bounds for the randomized Boppana-Halldórsson algorithm for MAXCLIQUE.- MNP: A class of NP optimization problems.- Semidefinite programming and its applications to NP problems.- Analysis and experimentation on list update algorithms.- An exact branch and bound algorithm for the Steiner Problem in Graphs.- A physical model for the satisfiability problem.- An efficient algorithm for local testability problem of finite state automata.- Scheduling task-tree with additive scales on parallel/distributed machines.- Single-vehicle scheduling problem on a straight line with time window constraints.- An on-line algorithm for some uniform processor Scheduling.- An algebraic characterization of tractable constraints.- Limit property of unbalanced development in economic network.- Document processing, theory, and practice.- Matching and comparing sequences in molecular biology.- Primal-dual schema based approximation algorithms.