๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Optimal on-line decremental connectivity in trees

โœ Scribed by Stephen Alstrup; Jens Peter Secher; Maz Spork

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
310 KB
Volume
64
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

Let T be a tree with n nodes from which edges are deleted interspersed with m on-line connectivity queries. Even and Shiloach gave an 0( n log n + m) algorithm to process edge deletion and m queries (Even and Shiloach, 1981). In this paper we present an O(n + m) algorithm for the same problem. @ 1997 Elsevier Science B.V.

๐Ÿ“œ SIMILAR VOLUMES

Optimal one-page tree embeddings in line
Optimal one-page tree embeddings in linear time
โœ Robert A. Hochberg; Matthias F. Stallmann ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 167 KB

In the minimum linear arrangement problem one wishes to assign distinct integers to the vertices of a given graph so that the sum of the differences (in absolute value) across the edges of the graph is minimized. This problem is known to be NP-complete for the class of all graphs, but polynomial for

On the largest tree of given maximum deg
On the largest tree of given maximum degree in a connected graph
โœ Y. Caro; I. Krasikov; Y. Roditty ๐Ÿ“‚ Article ๐Ÿ“… 1991 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 258 KB ๐Ÿ‘ 1 views

## Abstract We prove that every connected graph __G__ contains a tree __T__ of maximum degree at most __k__ that either spans __G__ or has order at least __k__ฮด(__G__) + 1, where ฮด(__G__) is the minimum degree of __G.__ This generalizes and unifies earlier results of Bermond [1] and Win [7]. We als

Nonlinear optimal on-line heat-dissipati
Nonlinear optimal on-line heat-dissipation control methodology in electronic devices
โœ Horng-Yuan Jang; Chung-Hsin Cheng ๐Ÿ“‚ Article ๐Ÿ“… 2009 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 900 KB

The essential element in obtaining semiconductor electronic device enhanced reliability involves solving the heat-dissipating issue. Certain electronic components possess varying thermal properties and the strength of the heat generated by the semiconductor chip is unknown. Therefore, the heat dissi