DYNAMIC CONNECTIVITY: SOME GRAPHS OF INTEREST
Journal: IADIS INTERNATIONAL JOURNAL ON COMPUTER SCIENCE AND INFORMATION SYSTEMS (Vol.16, No. 1)Publication Date: 2021-07-26
Authors : George Lagogiannis;
Page : 1-15
Keywords : ;
Abstract
In this paper we deal with the dynamic connectivity problem, targeting deterministic worst-case poly-logarithmic time-complexities. First we show that instead of solving the dynamic connectivity problem on a general graph G, it suffices to solve it on a graph we name aligned double-forest that has only 2n-1 edges where n is the number of vertices. Then we present an algorithm that achieves all the operations in logarithmic worst-case time on a graph we name star-tied forest that consists of a star and a forest (of trees), both defined on the same set of vertices. The star-tied forest which can be seen as a special case of an aligned double-forest is more complicated than a forest on which deterministic worst-case logarithmic time-complexities have already been obtained by means of the Dynamic Trees algorithm, introduced by Sleator and Tarjan (1983). For implementing the operations we build upon Dynamic Trees.
Other Latest Articles
- A HIDDEN MARKOV CHAIN APPROACH TO CROP YIELD FORECASTING
- HEAD MOVEMENTS IN THE IDLE LOOP ANIMATION
- NOVEL MUSIC INTERACTIONS: THE SUBJECTIVE EXPERIENCE IN BEGINNER AND EXPERT MUSICIANS
- KEY PERFORMANCE INDICATORS IN DESIGN FOR SUSTAINABLE RURAL TRANSPORT
- MODELLING SERIOUS GAMES FOR ENHANCING END USER CYBER SECURITY AWARENESS
Last modified: 2022-02-11 21:31:22