An efficient distributed algorithm for finding all hinge vertices in networks. (English) Zbl 1098.68143
Summary: Let \(G=(V,E)\) be a graph with vertex set \(V\) of size \(n\) and edge set \(E\) of size \(m\). A vertex \(v\in V\) is called a hinge vertex if there exist two vertices in \(V\setminus\{v\}\) such that their distance becomes longer when \(v\) is removed. In this paper, we present a distributed algorithm that finds all hinge vertices on an arbitrary graph. The proposed algorithm works for named static asynchronous networks and achieves \(O(n^2)\) time complexity and \(O(m)\) message complexity. In particular, the total messages exchanged during the algorithm are at most \(2m(\log n+n\log n+1)\) bits.
MSC:
| 68W15 | Distributed algorithms |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Ahuja M., Proceedings of the 9th Conference on Foundations of Software Technology and Theoretical Computer Scienc pp 99– |
| [2] | Chaudhuri P., Information Sciences 81 pp 73– (1994) · Zbl 0837.68042 · doi:10.1016/0020-0255(94)90090-6 |
| [3] | Korach E., ACM Transactions on Programming Languages and Systems 6 pp 380– (1984) · Zbl 0543.68051 · doi:10.1145/579.585 |
| [4] | Chang E. J.H., IEEE Transactions on Software Engineering 8 pp 391– (1982) · doi:10.1109/TSE.1982.235573 |
| [5] | Hohberg W., Journal of Parallel and Distributed Computing 9 pp 374– (1990) · doi:10.1016/0743-7315(90)90122-6 |
| [6] | Park J., Systems and Computers in Japan 22 pp 1– (1991) · doi:10.1002/scj.4690220801 |
| [7] | Awerbuch B., IEEE Transactions on Information Theory 33 pp 315– (1987) · Zbl 0629.68070 · doi:10.1109/TIT.1987.1057314 |
| [8] | Bui M., Journal of Parallel and Distributed Computing 64 pp 571– (2004) · Zbl 1106.68431 · doi:10.1016/j.jpdc.2004.03.009 |
| [9] | Gallager R. G., ACM Transactions in Programming Languages and Systems 5 pp 66– (1983) · Zbl 0498.68040 · doi:10.1145/357195.357200 |
| [10] | Lavallee I., Information Processing Letters 23 pp 55– (1986) · Zbl 0611.05015 · doi:10.1016/0020-0190(86)90043-8 |
| [11] | Farley A. M., Parallel Processing Letters 3 pp 381– (1993) · doi:10.1142/S0129626493000423 |
| [12] | Farley A. M., Graphs and Combinatorics 13 pp 345– (1997) · Zbl 0890.05059 · doi:10.1007/BF03353012 |
| [13] | Chang J. M., Taiwanese Journal of Mathematics 5 pp 789– (2001) |
| [14] | Chang J. M., Proceedings of the International Computer Symposium on Algorithms pp 105– (1996) |
| [15] | Chang J. M., Information Processing Letters 65 pp 81– (1998) · Zbl 1338.68214 · doi:10.1016/S0020-0190(97)00201-9 |
| [16] | Entringer R. C., IEEE Transactions on Circuits and Systems 24 pp 460– (1977) · Zbl 0344.05137 · doi:10.1109/TCS.1977.1084370 |
| [17] | Plesník J., Networks 41 pp 73– (2003) · Zbl 1014.05022 · doi:10.1002/net.10060 |
| [18] | Ho T. Y., Information Processing Letters 59 pp 103– (1996) · Zbl 0900.68331 · doi:10.1016/0020-0190(96)00092-0 |
| [19] | Bera D., Theory of Computing Systems 36 pp 17– (2003) · Zbl 1039.68088 · doi:10.1007/s00224-002-1004-3 |
| [20] | Honma H., IEICE Transactions on Information and Systems 84 pp 419– (2001) |
| [21] | Honma H., IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 85 pp 1031– (2002) |
| [22] | Bera D., Korean Journal of Computational and Applied Mathematics 8 pp 295– (2001) |
| [23] | Attiya H., Distributed Computing: Fundamentals, Simulations and Advanced Topics (1998) |
| [24] | Lynch N. A., Distributed Algorithms (1996) · Zbl 0877.68061 |
| [25] | Tell G., Distributed Algorithms (1994) · Zbl 0803.00026 · doi:10.1007/BFb0020419 |
| [26] | Awerbuch B., Proceedings of the 31st Annual ACM Symposium on Theory of Computing pp 490– (1989) |
| [27] | Awerbuch B., Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Scienc |
| [28] | Misra J., ACM Transactions on Programming Languages and Systems 4 pp 678– (1982) · Zbl 0489.68061 · doi:10.1145/69622.357190 |
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.
