Open Science Research Excellence

Open Science Index

Commenced in January 2007 Frequency: Monthly Edition: International Publications Count: 29284


Select areas to restrict search in scientific publication database:
12607
A Self-stabilizing Algorithm for Maximum Popular Matching of Strictly Ordered Preference Lists
Authors:
Abstract:
In this paper, we consider the problem of Popular Matching of strictly ordered preference lists. A Popular Matching is not guaranteed to exist in any network. We propose an IDbased, constant space, self-stabilizing algorithm that converges to a Maximum Popular Matching an optimum solution, if one exist. We show that the algorithm stabilizes in O(n5) moves under any scheduler (daemon).
Digital Object Identifier (DOI):

References:

[1] D. J. Abraham, R. W. Irving, T. Kavitha, and K. Mehlhorn. Popular matchings. SIAM J. Comput., 37(4):1030-1045, 2007.
[2] J. Beauquier, A. K. Datta, M. Gradinariu, and F. Magniette. Selfstabilizing local mutual exclusion and daemon refinement. In International Symposium on Distributed Computing, pages 223-237, 2000.
[3] E. W. Dijkstra. Self-stabilizing systems in spite of distributed control. Comm. ACM, 17(11):643-644, Jan. 1974.
[4] S. Dolev. Self-Stabilization. MIT Press, 2000.
[5] S. Dolev, A. Israeli, and S. Moran. Uniform dynamic self-stabilizing leader election. IEEE Trans. on Parallel and Distributed Systems, 8(4), 1995.
[6] D. Gale and L. S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69:9-15, 1962.
[7] P. Gardenfors. Match making: assignments based on bilateral preferences. Behavioral Sciences, 20:166-173, 1975.
[8] D. Gusfield and R. W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989.
[9] P. Hall. On representatives of subsets. Journal of the London Mathematical Society, 10:26-30, 1935.
[10] S. M. Hedetniemi, S. T. Hedetniemi, D. P. Jacobs, and P. K. Srimani. Self-stabilizing algorithms for minimal dominating sets and maximal independent sets. Comput. Math. Appl., 46(5-6):805-811, 2003.
[11] S.-C. Hsu and S.-T. Huang. A self-stabilizing algorithm for maximal matching. Inform. Process. Lett., 43:77-81, 1992.
[12] A. Panconesi and A. Srinivasan. The local nature of -coloring and its algorithmic applications. Combinatorica, 15:225-280, 1995.
[13] S. Rajagopalan and V. Vazirani. Primal-dual RNC approximation algorithms for set cover and covering integer programs. SIAM J. Comput., 28:525-540, 1998.
[14] Z. Shi, W. Goddard, and S. T. Hedetniemi. an anonymous selfstabilizing algorithm for 1-maximal independent set in trees. Information Processing Letters, 91(2):77-83, 2004.
[15] G. Tel. Introduction to Distributed Algorithms, Second Edition. Cambridge University Press, Cambridge UK, 2000.
Vol:13 No:02 2019Vol:13 No:01 2019
Vol:12 No:12 2018Vol:12 No:11 2018Vol:12 No:10 2018Vol:12 No:09 2018Vol:12 No:08 2018Vol:12 No:07 2018Vol:12 No:06 2018Vol:12 No:05 2018Vol:12 No:04 2018Vol:12 No:03 2018Vol:12 No:02 2018Vol:12 No:01 2018
Vol:11 No:12 2017Vol:11 No:11 2017Vol:11 No:10 2017Vol:11 No:09 2017Vol:11 No:08 2017Vol:11 No:07 2017Vol:11 No:06 2017Vol:11 No:05 2017Vol:11 No:04 2017Vol:11 No:03 2017Vol:11 No:02 2017Vol:11 No:01 2017
Vol:10 No:12 2016Vol:10 No:11 2016Vol:10 No:10 2016Vol:10 No:09 2016Vol:10 No:08 2016Vol:10 No:07 2016Vol:10 No:06 2016Vol:10 No:05 2016Vol:10 No:04 2016Vol:10 No:03 2016Vol:10 No:02 2016Vol:10 No:01 2016
Vol:9 No:12 2015Vol:9 No:11 2015Vol:9 No:10 2015Vol:9 No:09 2015Vol:9 No:08 2015Vol:9 No:07 2015Vol:9 No:06 2015Vol:9 No:05 2015Vol:9 No:04 2015Vol:9 No:03 2015Vol:9 No:02 2015Vol:9 No:01 2015
Vol:8 No:12 2014Vol:8 No:11 2014Vol:8 No:10 2014Vol:8 No:09 2014Vol:8 No:08 2014Vol:8 No:07 2014Vol:8 No:06 2014Vol:8 No:05 2014Vol:8 No:04 2014Vol:8 No:03 2014Vol:8 No:02 2014Vol:8 No:01 2014
Vol:7 No:12 2013Vol:7 No:11 2013Vol:7 No:10 2013Vol:7 No:09 2013Vol:7 No:08 2013Vol:7 No:07 2013Vol:7 No:06 2013Vol:7 No:05 2013Vol:7 No:04 2013Vol:7 No:03 2013Vol:7 No:02 2013Vol:7 No:01 2013
Vol:6 No:12 2012Vol:6 No:11 2012Vol:6 No:10 2012Vol:6 No:09 2012Vol:6 No:08 2012Vol:6 No:07 2012Vol:6 No:06 2012Vol:6 No:05 2012Vol:6 No:04 2012Vol:6 No:03 2012Vol:6 No:02 2012Vol:6 No:01 2012
Vol:5 No:12 2011Vol:5 No:11 2011Vol:5 No:10 2011Vol:5 No:09 2011Vol:5 No:08 2011Vol:5 No:07 2011Vol:5 No:06 2011Vol:5 No:05 2011Vol:5 No:04 2011Vol:5 No:03 2011Vol:5 No:02 2011Vol:5 No:01 2011
Vol:4 No:12 2010Vol:4 No:11 2010Vol:4 No:10 2010Vol:4 No:09 2010Vol:4 No:08 2010Vol:4 No:07 2010Vol:4 No:06 2010Vol:4 No:05 2010Vol:4 No:04 2010Vol:4 No:03 2010Vol:4 No:02 2010Vol:4 No:01 2010
Vol:3 No:12 2009Vol:3 No:11 2009Vol:3 No:10 2009Vol:3 No:09 2009Vol:3 No:08 2009Vol:3 No:07 2009Vol:3 No:06 2009Vol:3 No:05 2009Vol:3 No:04 2009Vol:3 No:03 2009Vol:3 No:02 2009Vol:3 No:01 2009
Vol:2 No:12 2008Vol:2 No:11 2008Vol:2 No:10 2008Vol:2 No:09 2008Vol:2 No:08 2008Vol:2 No:07 2008Vol:2 No:06 2008Vol:2 No:05 2008Vol:2 No:04 2008Vol:2 No:03 2008Vol:2 No:02 2008Vol:2 No:01 2008
Vol:1 No:12 2007Vol:1 No:11 2007Vol:1 No:10 2007Vol:1 No:09 2007Vol:1 No:08 2007Vol:1 No:07 2007Vol:1 No:06 2007Vol:1 No:05 2007Vol:1 No:04 2007Vol:1 No:03 2007Vol:1 No:02 2007Vol:1 No:01 2007