3 years ago

Maximum Matching on Trees in the Online Preemptive and the Incremental Dynamic Graph Models.

Sumedh Tirodkar, Sundar Vishwanathan

We study the Maximum Cardinality Matching (MCM) and the Maximum Weight Matching (MWM) problems, on trees and on some special classes of graphs, in the Online Preemptive and the Incremental Dynamic Graph models. In the {\em Online Preemptive} model, the edges of a graph are revealed one by one and the algorithm is required to always maintain a valid matching. On seeing an edge, the algorithm has to either accept or reject the edge. If accepted, then the adjacent edges are discarded, and all rejections are permanent. In this model, the complexity of the problems is settled for deterministic algorithms. Epstein et al. gave a $5.356$-competitive randomized algorithm for MWM, and also proved a lower bound of $1.693$ for MCM. The same lower bound applies for MWM.

In this paper we show that some of the results can be improved in the case of trees and some special classes of graphs. In the online preemptive model, we present a $64/33$-competitive (in expectation) randomized algorithm for MCM on trees.

Inspired by the above mentioned algorithm for MCM, we present the main result of the paper, a randomized algorithm for MCM with a "worst case" update time of $O(1)$, in the incremental dynamic graph model, which is $3/2$-approximate (in expectation) on trees, and $1.8$-approximate (in expectation) on general graphs with maximum degree $3$. Note that this algorithm works only against an oblivious adversary. Hence, we derandomize this algorithm, and give a $(3/2 + \epsilon)$-approximate deterministic algorithm for MCM on trees, with an amortized update time of $O(1/\epsilon)$.

We also present a minor result for MWM in the online preemptive model, a $3$-competitive (in expectation) randomized algorithm on growing trees (where the input revealed upto any stage is always a tree, i.e. a new edge never connects two disconnected trees).

Publisher URL: http://arxiv.org/abs/1612.05419

DOI: arXiv:1612.05419v3

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

  • Download from Google Play
  • Download from App Store
  • Download from AppInChina

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.