Abstract
Let G = (X, Y, E) be a bipartite graph with integer weights on the edges. Let n, m, and N denote the vertex count, the edge count, and an upper bound on the absolute values of edge weights of G, respectively. For a vertex u in G, let Gu denote the graph formed by deleting u from G. The all-cavity maximum matching problem asks for a maximum weight matching in Gu for all u in G. This problem finds applications in optimal tree algorithms for computational biology. We show that the problem is solvable in. (formula presented) time, matching the currently best time complexity for merely computing a single maximum weight matching in G. We also give an algorithm for a generalization of the problem where both a vertex from X and one from Y can be deleted. The running time is (formula presented). Our algorithms are based on novel linear-time reductions among problems of computing shortest paths and all-cavity maximum matchings.
| Original language | English (US) |
|---|---|
| Title of host publication | Algorithms and Computation - 8th International Symposium, ISAAC 1997, Proceedings |
| Editors | Hon Wai Leong, Sanjay Jain, Hiroshi Imai |
| Publisher | Springer Verlag |
| Pages | 364-373 |
| Number of pages | 10 |
| ISBN (Print) | 3540638903, 9783540638902 |
| DOIs | |
| State | Published - Jan 1 1997 |
| Event | 8th Annual International Symposium on Algorithms and Computation, ISAAC 1997 - Singapore, Singapore Duration: Dec 17 1997 → Dec 19 1997 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 1350 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Other
| Other | 8th Annual International Symposium on Algorithms and Computation, ISAAC 1997 |
|---|---|
| Country | Singapore |
| City | Singapore |
| Period | 12/17/97 → 12/19/97 |
Fingerprint
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)
Cite this
}
All-cavity maximum matchings. / Kao, Ming Yang; Lam, Tak Wah; Sung, Wing Kin; Ting, Hing Fung.
Algorithms and Computation - 8th International Symposium, ISAAC 1997, Proceedings. ed. / Hon Wai Leong; Sanjay Jain; Hiroshi Imai. Springer Verlag, 1997. p. 364-373 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1350).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
TY - GEN
T1 - All-cavity maximum matchings
AU - Kao, Ming Yang
AU - Lam, Tak Wah
AU - Sung, Wing Kin
AU - Ting, Hing Fung
PY - 1997/1/1
Y1 - 1997/1/1
N2 - Let G = (X, Y, E) be a bipartite graph with integer weights on the edges. Let n, m, and N denote the vertex count, the edge count, and an upper bound on the absolute values of edge weights of G, respectively. For a vertex u in G, let Gu denote the graph formed by deleting u from G. The all-cavity maximum matching problem asks for a maximum weight matching in Gu for all u in G. This problem finds applications in optimal tree algorithms for computational biology. We show that the problem is solvable in. (formula presented) time, matching the currently best time complexity for merely computing a single maximum weight matching in G. We also give an algorithm for a generalization of the problem where both a vertex from X and one from Y can be deleted. The running time is (formula presented). Our algorithms are based on novel linear-time reductions among problems of computing shortest paths and all-cavity maximum matchings.
AB - Let G = (X, Y, E) be a bipartite graph with integer weights on the edges. Let n, m, and N denote the vertex count, the edge count, and an upper bound on the absolute values of edge weights of G, respectively. For a vertex u in G, let Gu denote the graph formed by deleting u from G. The all-cavity maximum matching problem asks for a maximum weight matching in Gu for all u in G. This problem finds applications in optimal tree algorithms for computational biology. We show that the problem is solvable in. (formula presented) time, matching the currently best time complexity for merely computing a single maximum weight matching in G. We also give an algorithm for a generalization of the problem where both a vertex from X and one from Y can be deleted. The running time is (formula presented). Our algorithms are based on novel linear-time reductions among problems of computing shortest paths and all-cavity maximum matchings.
UR - http://www.scopus.com/inward/record.url?scp=84958045581&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958045581&partnerID=8YFLogxK
U2 - 10.1007/3-540-63890-3_39
DO - 10.1007/3-540-63890-3_39
M3 - Conference contribution
AN - SCOPUS:84958045581
SN - 3540638903
SN - 9783540638902
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 364
EP - 373
BT - Algorithms and Computation - 8th International Symposium, ISAAC 1997, Proceedings
A2 - Leong, Hon Wai
A2 - Jain, Sanjay
A2 - Imai, Hiroshi
PB - Springer Verlag
ER -