All-cavity maximum matchings

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

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

13 Scopus citations


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 languageEnglish (US)
Title of host publicationAlgorithms and Computation - 8th International Symposium, ISAAC 1997, Proceedings
EditorsHon Wai Leong, Sanjay Jain, Hiroshi Imai
PublisherSpringer Verlag
Number of pages10
ISBN (Print)3540638903, 9783540638902
StatePublished - Jan 1 1997
Event8th Annual International Symposium on Algorithms and Computation, ISAAC 1997 - Singapore, Singapore
Duration: Dec 17 1997Dec 19 1997

Publication series

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


Other8th Annual International Symposium on Algorithms and Computation, ISAAC 1997

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'All-cavity maximum matchings'. Together they form a unique fingerprint.

Cite this