### Abstract

Let G be a bipartite graph with positive integer weights on the edges and without isolated nodes. Let n and W be the node count and the total weight of G. We present a new decomposition theorem for maximum weight bipartite matchings and use it to design an O(√nW) -time algorithm for computing a maximum weight matching of G. This algorithm bridges a long-standing gap between the best known time complexity of computing a maximum weight matching and that of computing a maximum cardinality matching. Given G and a maximum weight matching of G, we can further compute the weight of a maximum weight matching of G — {u} for all nodes u in O(W) time. As immediate applications of these algorithms, the best known time complexity of computing a maximum agreement subtree of two ℓ-leaf rooted or unrooted evolutionary trees is reduced from O(ℓ^{1.5} log ℓ) to O(l^{1.5}).

Original language | English (US) |
---|---|

Title of host publication | Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings |

Editors | Jaroslav Nešetřil |

Publisher | Springer Verlag |

Pages | 438-449 |

Number of pages | 12 |

ISBN (Print) | 3540662510, 9783540662518 |

DOIs | |

State | Published - Jan 1 1999 |

Event | 7th Annual European Symposium on Algorithms, ESA 1999 - Prague, Czech Republic Duration: Jul 16 1999 → Jul 18 1999 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1643 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 7th Annual European Symposium on Algorithms, ESA 1999 |
---|---|

Country | Czech Republic |

City | Prague |

Period | 7/16/99 → 7/18/99 |

### Fingerprint

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings*(pp. 438-449). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1643). Springer Verlag. https://doi.org/10.1007/3-540-48481-7_38

}

*Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings.*Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1643, Springer Verlag, pp. 438-449, 7th Annual European Symposium on Algorithms, ESA 1999, Prague, Czech Republic, 7/16/99. https://doi.org/10.1007/3-540-48481-7_38

**A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees.** / Kao, Ming Yang; Lam, Tak Wah; Sung, Wing Kin; Ting, Hing Fung.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees

AU - Kao, Ming Yang

AU - Lam, Tak Wah

AU - Sung, Wing Kin

AU - Ting, Hing Fung

PY - 1999/1/1

Y1 - 1999/1/1

N2 - Let G be a bipartite graph with positive integer weights on the edges and without isolated nodes. Let n and W be the node count and the total weight of G. We present a new decomposition theorem for maximum weight bipartite matchings and use it to design an O(√nW) -time algorithm for computing a maximum weight matching of G. This algorithm bridges a long-standing gap between the best known time complexity of computing a maximum weight matching and that of computing a maximum cardinality matching. Given G and a maximum weight matching of G, we can further compute the weight of a maximum weight matching of G — {u} for all nodes u in O(W) time. As immediate applications of these algorithms, the best known time complexity of computing a maximum agreement subtree of two ℓ-leaf rooted or unrooted evolutionary trees is reduced from O(ℓ1.5 log ℓ) to O(l1.5).

AB - Let G be a bipartite graph with positive integer weights on the edges and without isolated nodes. Let n and W be the node count and the total weight of G. We present a new decomposition theorem for maximum weight bipartite matchings and use it to design an O(√nW) -time algorithm for computing a maximum weight matching of G. This algorithm bridges a long-standing gap between the best known time complexity of computing a maximum weight matching and that of computing a maximum cardinality matching. Given G and a maximum weight matching of G, we can further compute the weight of a maximum weight matching of G — {u} for all nodes u in O(W) time. As immediate applications of these algorithms, the best known time complexity of computing a maximum agreement subtree of two ℓ-leaf rooted or unrooted evolutionary trees is reduced from O(ℓ1.5 log ℓ) to O(l1.5).

UR - http://www.scopus.com/inward/record.url?scp=84958038951&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958038951&partnerID=8YFLogxK

U2 - 10.1007/3-540-48481-7_38

DO - 10.1007/3-540-48481-7_38

M3 - Conference contribution

AN - SCOPUS:84958038951

SN - 3540662510

SN - 9783540662518

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 438

EP - 449

BT - Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings

A2 - Nešetřil, Jaroslav

PB - Springer Verlag

ER -