File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: All-cavity maximum Matchings

TitleAll-cavity maximum Matchings
Authors
Issue Date1997
PublisherSpringer.
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?
AbstractLet 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 Identifierhttp://hdl.handle.net/10722/93016
ISBN
ISSN
2023 SCImago Journal Rankings: 0.606
Series/Report no.Lecture Notes in Computer Science book series (LNCS, volume 1350)

 

DC FieldValueLanguage
dc.contributor.authorKao, MYen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorSung, WKen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2010-09-25T14:48:19Z-
dc.date.available2010-09-25T14:48:19Z-
dc.date.issued1997en_HK
dc.identifier.citationInternational 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.isbn978-3-540-63890-2-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/93016-
dc.description.abstractLet 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.languageengen_HK
dc.publisherSpringer.-
dc.relation.ispartofInternational Symposium on Algorithms And Computationen_HK
dc.relation.ispartofseriesLecture Notes in Computer Science book series (LNCS, volume 1350)-
dc.titleAll-cavity maximum Matchingsen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailLam, TW: twlam@cs.hku.hken_HK
dc.identifier.emailTing, HF: hfting@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/3-540-63890-3_39-
dc.identifier.scopuseid_2-s2.0-84958045581-
dc.identifier.hkuros25409en_HK
dc.identifier.eissn1611-3349-
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats