An O (log (n)) Fully Dynamic Algorithm for Maximum matching in a tree
In this paper, we have developed a fully-dynamic algorithm for maintaining cardinality of
maximum-matching in a tree using the construction of top-trees. The time complexities are
as follows: 1. Initialization Time: $ O (n (log (n))) $ to build the Top-tree. 2. Update Time: $ O
(log (n)) $3. Query Time: O (1) to query the cardinality of maximum-matching and $ O (log
(n)) $ to find if a particular edge is matched.
maximum-matching in a tree using the construction of top-trees. The time complexities are
as follows: 1. Initialization Time: $ O (n (log (n))) $ to build the Top-tree. 2. Update Time: $ O
(log (n)) $3. Query Time: O (1) to query the cardinality of maximum-matching and $ O (log
(n)) $ to find if a particular edge is matched.
In this paper, we have developed a fully-dynamic algorithm for maintaining cardinality of maximum-matching in a tree using the construction of top-trees. The time complexities are as follows: 1. Initialization Time: to build the Top-tree. 2. Update Time: 3. Query Time: O(1) to query the cardinality of maximum-matching and to find if a particular edge is matched.
arxiv.org