Titlebook: STACS 98; 15th Annual Symposiu Michel Morvan,Christoph Meinel,Daniel Krob Conference proceedings 1998 Springer-Verlag Berlin Heidelberg 199

verdict

广告

cyanosis

The complexity of modular graph automorphism,e an appropriate search version of Mod.GA and design an algorithm that polynomial-time reduces the Mod.GA search problem to the decision problem. Combining this algorithm with an IP protocol, we obtain a randomized polynomial-time checker for Mod.GA, for all . > 1.

PHON

A synthesis on partition refinement: A useful routine for strings, graphs, boolean matrices and aute class of potentially new problems. Our framework yields to a unique scheme for correctness proofs and complexity analysis. Various examples are presented to show the different ways of using this routine.

事情

河潭

The complexity of propositional linear temporal logics in simple cases, practice..In this paper we investigate this issue and consider model-checking and satisfiability for all fragments of PLTL one obtains when restrictions are put on (1) the temporal connectives allowed, (2) the number of atomic propositions, and (3) the temporal height.

拥护者

Palpitation

Distributed online frequency assignment in cellular networks,uch algorithms that utilize information about increasingly larger neighborhoods around nodes, and thereby achieve progressively better competitive ratios. We also exhibit lower bounds on the competitive ratios of some natural classes of distributed online algorithms for the problem; in some cases, our bounds are shown to be optimal.

松紧带

平项山

Searching constant width mazes captures the A,, hierarchy, graphs is complete for ... As an application, we show that there is a data structure solving dynamic st-connectivity for con stant width grid graphs with time bound .(log log .) per operation on a random access machine. The dynamic algorithm is derived from the parallel one in an indirect way using algebraic tools.