We show how to compute a maximum cardinality matching in a bipartite graph of n vertices
in time O (n 1.5 m log n). For dense graphs this improves on the O (nm) algorithm of Hopcroft
and Karp. The speed-up is obtained by an application of the fast adjacency matrix scanning …

Silica chimneys were discovered in 1985 at 86° W in the rift valley of the Galapagos
Spreading Center at 2600 m depth (“Cauliflower Garden”). The inactive chimneys lack any
sulfides and consist almost entirely of amorphous silica (up to 96 wt.% SiO 2, opal-A); Fe …

The Hess Deep, a rifted oval‐shaped depression located east of the Galapagos Triple
Junction at the tip of the Cocos‐Nazca ridge (about 101° W, 2° N), was explored in 1988
during 21 submersible dives. A total of 11 dives were devoted to the exploration of the E‐W …

Abstract. Paul (1977) has proved a 2.5n-lower bound for the network complexity of an explicit
Boolean function. We modify the definition of Paul's function slightly and prove a 3n-lower bound
for the network complexity of that function … One of the most difficult problems in complexity …

We give an algorithm for the disjoint set union problem, within the class of algorithms
defined by Tarjan, which has O(\logn/\log\logn) single-operation time complexity in the worst
case. Also we define a class of algorithms for the disjoint set union problem, which includes …

0n the Average Number of Reba lanc i ng 0 pera ti on sin Weight-Bal an ced Trees by Norbert
B l um Kur t Meh 1 h 0 rn Fach b er eich 10 U niv ers i tät des Sa arla ndes 66 OO Saarbrücken
West-Germany А — 78/06 June 1978 Pbstract: It is shown that the average number of rebalancing …

We reduce the problem of finding an augmenting path in a general graph to a reachability
problem and show that a slight modification of depth-first search leads to an algorithm for
finding such paths. As a consequence, we obtain a straightforward algorithm for maximum …

Hydrothermal activity is fairly well documented from most mid-ocean ridges. However,
despite various efforts there is only one hydrothermal field recognized so far in the Indian
Ocean. Products of former hydrothermal activity were sampled in the fourth segment of the …

More than 20 years ago, Hopcroft (1971) has given an algorithm for minimizing an n-state
finite automaton in O (kn log n) time where k is the size of the alphabet. This contrasts to the
usual O (kn 2) algorithms presented in text books. Since Hopcroft's algorithm changes the …

We develop a new method for placing a given context-free grammar into Greibach normal
form with only polynomial increase of its size. Starting with an arbitrary"-free context-free
grammar G, we transform G into an equivalent context-free grammar H in extended Greibach …