×

A self-stabilizing algorithm for constructing a minimal reachable directed acyclic graph with two senders and two targets. (English) Zbl 1504.68173

Summary: In this paper, we introduce a new graph structure named an \(\mathcal{ST}\)-reachable directed acyclic graph which is a directed acyclic graph (DAG) that guarantees reachability (i.e., a directed path exists) from every sender to every target. When an arbitrarily connected undirected graph \(G = (V, E)\) and two sets of the vertices, senders \(\mathcal{S}\) (\(\subset V\)) and targets \(\mathcal{T}\) (\(\subset V\)), are given, we consider the construction of a minimal \(\mathcal{ST} \)-reachable DAG by changing some undirected edges to arcs and removing the remaining edges.
In this paper, we present the necessary and sufficient condition under which a minimal \(\mathcal{ST} \)-reachable DAG can be constructed when \(| \mathcal{S} | \leq 2\) and \(| \mathcal{T} | \leq 2\), and propose a self-stabilizing algorithm for constructing a minimal \(\mathcal{ST} \)-reachable DAG (if it exists) when an arbitrarily connected undirected graph, \( \mathcal{S}\) (\(| \mathcal{S} | \leq 2\)) and \(\mathcal{T}\) (\(| \mathcal{T} | \leq 2\)) are given. Moreover, our proposed algorithm can detect the non-existence of any \(\mathcal{ST} \)-reachable DAG if the \(\mathcal{ST} \)-reachable DAG of the given graph and two sets of vertices, \( \mathcal{S}\) and \(\mathcal{T} \), do not exist.

MSC:

68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aharoni, Ron, Menger’s theorem for graphs containing no infinite paths, Eur. J. Comb., 4, 3, 201-204 (1983) · Zbl 0525.05043
[2] Aranha, Rohan F. M.; Rangan, C. Pandu, An efficient distributed algorithm for st-numbering the vertices of a biconnected graph, J. Univers. Comput. Sci., 1, 9, 633-650 (1995) · Zbl 0960.68784
[3] Atzori, Luigi; Iera, Antonio; Morabito, Giacomo, The internet of things: a survey, Comput. Netw., 54, 15, 2787-2805 (October 2010)
[4] Brandes, Ulrik, Eager st-ordering, (Mohring, Rolf; Raman, Rajeev, Algorithms — ESA 2002 (2002), Springer: Springer Berlin, Heidelberg), 247-256 · Zbl 1019.68803
[5] Chaudhuri, Pranay; Thompson, Hussein, A self-stabilizing algorithm for the st-order problem, Int. J. Parallel Emerg. Distrib. Syst., 23, 3, 219-234 (2008) · Zbl 1147.68880
[6] Datta, A. K.; Gurumurthy, S.; Petit, F.; Villain, V., Self-stabilizing network orientation algorithms in arbitrary rooted networks, (Proceedings 20th IEEE International Conference on Distributed Computing Systems (2000)), 576-583
[7] Datta, Ajoy; Larmore, Lawrence; Devismes, Stéphane; Heurtefeux, Karel; Rivierre, Yvan, Self-stabilizing small k-dominating sets, Int. J. Networking Comput., 3, 1, 116-136 (2013)
[8] de Morais Cordeiro, Carlos; Prakash Agrawal, Dharma, Ad Hoc and Sensor Networks: Theory and Applications (2011), World Scientific Publishing Co., Inc.: World Scientific Publishing Co., Inc. River Edge, NJ, USA
[9] Devismes, Stéphane, A silent self-stabilizing algorithm for finding cut-nodes and bridges, Parallel Process. Lett., 15(01n02), 183-198 (2005)
[10] Dijkstra, Edsger W., Self-stabilizing systems in spite of distributed control, Commun. ACM, 17, 11, 643-644 (November 1974)
[11] Ebert, J., st-Ordering the vertices of biconnected graphs, Computing, 30, 1, 19-33 (1983) · Zbl 0491.05057
[12] Shimon, Even; Tarjan, Robert Endre, Computing an st-numbering, Theor. Comput. Sci., 2, 3, 339-344 (1976) · Zbl 0341.68029
[13] Green, D. B.; Obaidat, M. S., Modeling and simulation of IEEE 802.11 wlan mobile ad hoc networks using topology broadcast reverse-path forwarding (tbrpf), Comput. Commun., 26, 15, 1741-1746 (September 2003)
[14] Hadid, Rachid; Karaata, Mehmet Hakan; Villain, Vincent, A stabilizing algorithm for finding two node-disjoint paths in arbitrary networks, Int. J. Found. Comput. Sci., 28, 04, 411-435 (2017) · Zbl 1372.68029
[15] Jacquet, P.; Muhlethaler, P.; Clausen, T.; Laouiti, A.; Qayyum, A.; Viennot, L., Optimized link state routing protocol for ad hoc networks, (Proceedings. IEEE International Multi Topic Conference, 2001. IEEE INMIC 2001. Technology for the 21st Century (2001)), 62-68
[16] Karaata, Mehmet Hakan, A stabilizing algorithm for finding biconnected components, J. Parallel Distrib. Comput., 62, 5, 982-999 (2002) · Zbl 1004.68020
[17] Karaata, Mehmet Hakan; Chaudhuri, Pranay, A dynamic self-stabilizing algorithm for constructing a transport net, Computing, 68, 2, 143-161 (2002) · Zbl 1002.68014
[18] Kim, Yonghwan; Aono, Hiroki; Katayama, Yoshiaki; Masuzawa, Toshimitsu, A self-stabilizing algorithm for constructing a maximal (2, 2)-directed acyclic mixed graph, (Proceedings of the Sixth International Symposium on Computer and Networking (2018))
[19] Kim, Yonghwan; Ohno, Haruka; Katayama, Yoshiaki; Masuzawa, Toshimitsu, A self-stabilizing algorithm for constructing (1, 1)-maximal directed acyclic graph, (2017 IEEE International Parallel and Distributed Processing Symposium Workshops. 2017 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW (2017)), 844-853
[20] Kim, Yonghwan; Ohno, Haruka; Katayama, Yoshiaki; Masuzawa, Toshimitsu, A self-stabilizing algorithm for constructing a maximal (1, 1)-directed acyclic mixed graph, Int. J. Networking Comput., 8, 1, 53-72 (2018)
[21] Kim, Yonghwan; Shibata, Masahiro; Sudo, Yuichi; Nakamura, Junya; Katayama, Yoshiaki; Masuzawa, Toshimitsu, A self-stabilizing algorithm for constructing an st-reachable directed acyclic graph when \(| \mathcal{S} | \leq 2\) and \(| \mathcal{T} | \leq 2\), (39th IEEE International Conference on Distributed Computing Systems. 39th IEEE International Conference on Distributed Computing Systems, ICDCS 2019 (2019))
[22] Mahesh Kumar, K. M.; Sunitha, N. R.; Mathew, R.; Veerayya, M.; Vijendra, C., Secure ad-hoc on-demand distance vector routing using identity based symmetric key management, (2016 International Conference on Wireless Communications, Signal Processing and Networking. 2016 International Conference on Wireless Communications, Signal Processing and Networking, WiSPNET (2016)), 1075-1081
[23] Nakamura, Junya; Shibata, Masahiro; Sudo, Yuichi; Kim, Yonghwan, Self-stabilizing construction of a minimal weakly st-reachable directed acyclic graph, (International Symposium on Reliable Distributed Systems. International Symposium on Reliable Distributed Systems, SRDS 2020 (2020)), 1-10
[24] Wilson, Robin J., Introduction to Graph Theory (1986), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. USA · Zbl 0891.05001
[25] Zheng, Jun; Jamalipour, Abbas, Wireless Sensor Networks: A Networking Perspective (2009), Wiley-IEEE Press · Zbl 1185.68058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.