Unbalanced and hierarchical bipartite matchings with applications to labeled tree comparison

Ming Yang Kao, Tak Wah Lam, Wing Kin Sung, Hing Fung Ting

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper is concerned with maximum weight matchings of bipartite graphs. We show how to speed up the existing matching algorithms when the input graphs are node unbalanced or weight unbalanced. Based on these improved matching algorithms, we can solve efficiently a new matching problem called the hierarchical bipartite matching problem, and thus obtain a simple and faster algoirthm for finding the maximum agreement subtree of two labeled trees. The significance of our subtree algorithm lies in the fact that it matches or outperforms all previously known subtree algorithms that were designed for two special cases of labeled trees, namely, uniformly labeled trees and evolutionary trees.

Original languageEnglish (US)
Title of host publicationAlgorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings
EditorsD.T. Lee, Shang-Hua Teng, Shang-Hua Teng
PublisherSpringer Verlag
Pages479-490
Number of pages12
ISBN (Print)3540412557, 9783540412557
StatePublished - Jan 1 2000
Event11th Annual International Symposium on Algorithms and Computation, ISAAC 2000 - Taipei, Taiwan, Province of China
Duration: Dec 18 2000Dec 20 2000

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1969
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other11th Annual International Symposium on Algorithms and Computation, ISAAC 2000
CountryTaiwan, Province of China
CityTaipei
Period12/18/0012/20/00

Fingerprint

Bipartite Matching
Labeled Trees
Matching Problem
Matching Algorithm
Evolutionary Tree
Bipartite Graph
Speedup
Graph in graph theory
Vertex of a graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Kao, M. Y., Lam, T. W., Sung, W. K., & Ting, H. F. (2000). Unbalanced and hierarchical bipartite matchings with applications to labeled tree comparison. In D. T. Lee, S-H. Teng, & S-H. Teng (Eds.), Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings (pp. 479-490). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1969). Springer Verlag.
Kao, Ming Yang ; Lam, Tak Wah ; Sung, Wing Kin ; Ting, Hing Fung. / Unbalanced and hierarchical bipartite matchings with applications to labeled tree comparison. Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. editor / D.T. Lee ; Shang-Hua Teng ; Shang-Hua Teng. Springer Verlag, 2000. pp. 479-490 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{5eadf3006ee542e68de087e15f6d9f9d,
title = "Unbalanced and hierarchical bipartite matchings with applications to labeled tree comparison",
abstract = "This paper is concerned with maximum weight matchings of bipartite graphs. We show how to speed up the existing matching algorithms when the input graphs are node unbalanced or weight unbalanced. Based on these improved matching algorithms, we can solve efficiently a new matching problem called the hierarchical bipartite matching problem, and thus obtain a simple and faster algoirthm for finding the maximum agreement subtree of two labeled trees. The significance of our subtree algorithm lies in the fact that it matches or outperforms all previously known subtree algorithms that were designed for two special cases of labeled trees, namely, uniformly labeled trees and evolutionary trees.",
author = "Kao, {Ming Yang} and Lam, {Tak Wah} and Sung, {Wing Kin} and Ting, {Hing Fung}",
year = "2000",
month = "1",
day = "1",
language = "English (US)",
isbn = "3540412557",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "479--490",
editor = "D.T. Lee and Shang-Hua Teng and Shang-Hua Teng",
booktitle = "Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings",
address = "Germany",

}

Kao, MY, Lam, TW, Sung, WK & Ting, HF 2000, Unbalanced and hierarchical bipartite matchings with applications to labeled tree comparison. in DT Lee, S-H Teng & S-H Teng (eds), Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1969, Springer Verlag, pp. 479-490, 11th Annual International Symposium on Algorithms and Computation, ISAAC 2000, Taipei, Taiwan, Province of China, 12/18/00.

Unbalanced and hierarchical bipartite matchings with applications to labeled tree comparison. / Kao, Ming Yang; Lam, Tak Wah; Sung, Wing Kin; Ting, Hing Fung.

Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. ed. / D.T. Lee; Shang-Hua Teng; Shang-Hua Teng. Springer Verlag, 2000. p. 479-490 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1969).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Unbalanced and hierarchical bipartite matchings with applications to labeled tree comparison

AU - Kao, Ming Yang

AU - Lam, Tak Wah

AU - Sung, Wing Kin

AU - Ting, Hing Fung

PY - 2000/1/1

Y1 - 2000/1/1

N2 - This paper is concerned with maximum weight matchings of bipartite graphs. We show how to speed up the existing matching algorithms when the input graphs are node unbalanced or weight unbalanced. Based on these improved matching algorithms, we can solve efficiently a new matching problem called the hierarchical bipartite matching problem, and thus obtain a simple and faster algoirthm for finding the maximum agreement subtree of two labeled trees. The significance of our subtree algorithm lies in the fact that it matches or outperforms all previously known subtree algorithms that were designed for two special cases of labeled trees, namely, uniformly labeled trees and evolutionary trees.

AB - This paper is concerned with maximum weight matchings of bipartite graphs. We show how to speed up the existing matching algorithms when the input graphs are node unbalanced or weight unbalanced. Based on these improved matching algorithms, we can solve efficiently a new matching problem called the hierarchical bipartite matching problem, and thus obtain a simple and faster algoirthm for finding the maximum agreement subtree of two labeled trees. The significance of our subtree algorithm lies in the fact that it matches or outperforms all previously known subtree algorithms that were designed for two special cases of labeled trees, namely, uniformly labeled trees and evolutionary trees.

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

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

M3 - Conference contribution

AN - SCOPUS:84949895620

SN - 3540412557

SN - 9783540412557

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

SP - 479

EP - 490

BT - Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings

A2 - Lee, D.T.

A2 - Teng, Shang-Hua

A2 - Teng, Shang-Hua

PB - Springer Verlag

ER -

Kao MY, Lam TW, Sung WK, Ting HF. Unbalanced and hierarchical bipartite matchings with applications to labeled tree comparison. In Lee DT, Teng S-H, Teng S-H, editors, Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. Springer Verlag. 2000. p. 479-490. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).