Aubin Jarry
ABSTRACT
The evolving graph model was developed to capture the information on the topology of dynamic networks in a compact and efficient manner [5]. It is known that to find the size of the maximum strongly connected component in evolving graphs is NP-hard [1]. In this paper we study the strongly connected component in evolving graphs with geometric properties. We show that SCC is still NP-hard in the case the nodes are placed on a grid and two points are connected if the Euclidean distance is equal or less than 2. On the other hand we show that if the underlying graph is tree this problem can be solved in polynomial time.
- S. Bhadra and A. Ferreira. Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In S. Pierre, M. Barbeau, and E. Kranakis, editors, Proceedings of Adhoc-Now'03, volume 2865 of Lecture Notes in Computer Science, pages 259--270, Montreal, October 2003. Springer Verlag.Google Scholar
- A. Borodin and R. El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998. Google ScholarDigital Library
- A. Faragò and V.R. Syrotiuk. A unified framework for routing protocol. Proceedings ACM Mobicom 01, pages 53--60, 2001. Google ScholarDigital Library
- A. Ferreira and A. Jarry. Complexity of minimum spanning tree in evolving graphs and the minimum-energy broadcast routing problem. In Proceedings of WiOpt'04: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, University of Cambridge, UK, March 2004.Google Scholar
- Afonso Ferreira. Building a reference combinatorial model for dynamic networks: Initial results on evolving graphs. Technical Report RR-5041, INRIA, 2003.Google Scholar
- B. Bui Xuan, A. Ferreira, and A. Jarry. Computing shortest, fastest and foremost journeys in wireless dynamic networks. WiOpt'03, 2003.Google Scholar
Index Terms
- Connectivity in evolving graph with geometric properties
Recommendations
Connectivity Keeping Trees in 2-Connected Graphs with Girth Conditions
AbstractMader conjectured in 2010 that for any tree T of order m, every k-connected graph G with minimum degree at least contains a subtree such that is k-connected. This conjecture has been proved for ; however, it remains open ...
Connectivity Keeping Trees in 2-Connected Graphs with Girth Conditions
Combinatorial AlgorithmsAbstractMader conjectured in 2010 that for any tree T of order m, every k-connected graph G with minimum degree at least contains a subtree such that is k-connected. This conjecture has been proved for ; however, it remains open for general ; for , ...
The bondage and connectivity of a graph
Let G =(V,E) be a simple graph. A subset S of V is a dominating set of G if for any vertex v ∈ V - S, there exists some vertex u ∈ S such that uv ∈ E(G). The domination number, denoted by γ(G), is the cardinality of a minimum dominating set of G. The ...
Comments