### 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