Maximum Matching on Trees in the Online Preemptive and the Incremental Dynamic Graph Models
作者： Sumedh Tirodkar , Sundar Vishwanathan
DOI: 10.1007/978-3-319-62389-4_42
关键词:
摘要: We study the Maximum Cardinality Matching (MCM) and Weight (MWM) problems, on trees some special classes of graphs, in Online Preemptive Incremental Dynamic Graph models. In model, edges a graph are revealed one by algorithm is required to always maintain valid matching. On seeing an edge, has either accept or reject edge. If accepted, then adjacent discarded, all rejections permanent. this complexity problems settled for deterministic algorithms [11, 15]. Epstein et al. [5] gave 5.356-competitive randomized MWM, also proved lower bound 1.693 MCM. The same applies MWM.
springer.com
harvard.edu
arxiv.org
arxiv-vanity.com参考文章(19)
Ashish Chiplunkar, Sumedh Tirodkar, Sundar Vishwanathan, On Randomized Algorithms for Matching in the Online Preemptive Model european symposium on algorithms. pp. 325- 336 ,(2015) , 10.1007/978-3-662-48350-3_28
Andrew McGregor, Finding Graph Matchings in Data Streams Lecture Notes in Computer Science. pp. 170- 181 ,(2005) , 10.1007/11538462_15
Richard Peng, Manoj Gupta, Fully Dynamic $(1+\epsilon)$-Approximate Matchings arXiv: Data Structures and Algorithms. ,(2013)
B. V. Ashwinkumar, Buyback Problem - Approximate matroid intersection with cancellation costs arXiv: Computer Science and Game Theory. ,(2010) , 10.1007/978-3-642-22006-7_32
B. Kalyanasundaram, K. Pruhs, Online weighted matching Journal of Algorithms. ,vol. 14, pp. 478- 488 ,(1993) , 10.1006/JAGM.1993.1026
Manoj Gupta, Richard Peng, Fully Dynamic (1+ e)-Approximate Matchings 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. pp. 548- 557 ,(2013) , 10.1109/FOCS.2013.65
R. M. Karp, U. V. Vazirani, V. V. Vazirani, An optimal algorithm for on-line bipartite matching symposium on the theory of computing. pp. 352- 358 ,(1990) , 10.1145/100216.100262
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang, On graph problems in a semi-streaming model Theoretical Computer Science. ,vol. 348, pp. 207- 216 ,(2005) , 10.1016/J.TCS.2005.09.013
Cliff Stein, Aaron Bernstein, Faster fully dynamic matchings with small approximation ratios symposium on discrete algorithms. pp. 692- 711 ,(2016) , 10.5555/2884435.2884485
Manoj Gupta, Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time foundations of software technology and theoretical computer science. ,vol. 29, pp. 227- 239 ,(2014) , 10.4230/LIPICS.FSTTCS.2014.227