File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/3-540-63890-3_39
- Scopus: eid_2-s2.0-84958045581
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: All-cavity maximum Matchings
| Title | All-cavity maximum Matchings |
|---|---|
| Authors | |
| Issue Date | 1997 |
| Publisher | Springer. |
| Citation | International Symposium on Algorithms And Computation, Singapore, 17-19 December 1997. In Leong, HW, Imai, H and Jain, S (Eds.). Algorithms and Computation: 8th International Symposium, ISAAC '97 Singapore, December 17–19, 1997 Proceedings, p. 364-373. Berlin, Heidelberg: Springer, 1997 How to Cite? |
| 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 O(√nmlog(nN)) 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 O(n21og n + nm). Our algorithms are based on novel linear-time reductions among problems of computing shortest paths and all-cavity maximum matchings.
Research supported in part by NSF Grants CCR-9531028.
Research supported in part by RGC (The Research Grants Council of Hong Kong) Grants 338/065/0027 and 338/065/0028. |
| Persistent Identifier | http://hdl.handle.net/10722/93016 |
| ISBN | |
| ISSN | 2020 SCImago Journal Rankings: 0.249 |
| Series/Report no. | Lecture Notes in Computer Science book series (LNCS, volume 1350) |
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Kao, MY | en_HK |
| dc.contributor.author | Lam, TW | en_HK |
| dc.contributor.author | Sung, WK | en_HK |
| dc.contributor.author | Ting, HF | en_HK |
| dc.date.accessioned | 2010-09-25T14:48:19Z | - |
| dc.date.available | 2010-09-25T14:48:19Z | - |
| dc.date.issued | 1997 | en_HK |
| dc.identifier.citation | International Symposium on Algorithms And Computation, Singapore, 17-19 December 1997. In Leong, HW, Imai, H and Jain, S (Eds.). Algorithms and Computation: 8th International Symposium, ISAAC '97 Singapore, December 17–19, 1997 Proceedings, p. 364-373. Berlin, Heidelberg: Springer, 1997 | - |
| dc.identifier.isbn | 978-3-540-63890-2 | - |
| dc.identifier.issn | 0302-9743 | - |
| dc.identifier.uri | http://hdl.handle.net/10722/93016 | - |
| dc.description.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 O(√nmlog(nN)) 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 O(n21og n + nm). Our algorithms are based on novel linear-time reductions among problems of computing shortest paths and all-cavity maximum matchings. Research supported in part by NSF Grants CCR-9531028. Research supported in part by RGC (The Research Grants Council of Hong Kong) Grants 338/065/0027 and 338/065/0028. | - |
| dc.language | eng | en_HK |
| dc.publisher | Springer. | - |
| dc.relation.ispartof | International Symposium on Algorithms And Computation | en_HK |
| dc.relation.ispartofseries | Lecture Notes in Computer Science book series (LNCS, volume 1350) | - |
| dc.title | All-cavity maximum Matchings | en_HK |
| dc.type | Conference_Paper | en_HK |
| dc.identifier.email | Lam, TW: twlam@cs.hku.hk | en_HK |
| dc.identifier.email | Ting, HF: hfting@cs.hku.hk | en_HK |
| dc.identifier.authority | Lam, TW=rp00135 | en_HK |
| dc.identifier.authority | Ting, HF=rp00177 | en_HK |
| dc.description.nature | link_to_subscribed_fulltext | - |
| dc.identifier.doi | 10.1007/3-540-63890-3_39 | - |
| dc.identifier.scopus | eid_2-s2.0-84958045581 | - |
| dc.identifier.hkuros | 25409 | en_HK |
| dc.identifier.eissn | 1611-3349 | - |
| dc.identifier.issnl | 0302-9743 | - |