Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR95-002 | 1st January 1995
Detlef Sieling

New Lower Bounds and Hierarchy Results for Restricted Branching Programs

In unrestricted branching programs all variables may be tested
arbitrarily often on each path. But exponential lower bounds are only
known, if on each path the number of tests of each variable is bounded
(Borodin, Razborov and Smolensky (1993)). We examine branching programs
in which for each path the ... more >>>


TR95-007 | 1st January 1995
U. Faigle, S.P. Fekete, W. Hochstättler, W. Kern

THE NUCLEON OF COOPERATIVE GAMES AND AN ALGORITHM FOR MATCHING GAMES

The {\it nucleon} is introduced as a new allocation concept for
non-negative cooperative n-person transferable utility games.
The nucleon may be viewed as the multiplicative analogue of
Schmeidler's nucleolus.
It is shown that the nucleon of (not necessarily bipartite) matching
games ... more >>>


TR95-003 | 1st January 1995
Marek Karpinski, Alexander Zelikovsky

1.757 and 1.267-Approximation Algorithms for the Network and and Rectilinear Steiner Tree Problems

The Steiner tree problem requires to find a shortest tree connection
a given set of terminal points in a metric space. We suggest a better
and fast heuristic for the Steiner problem in graphs and in
rectilinear plane. This heuristic finds a Steiner tree at ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint