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 Citations (Scopus)

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 languageEnglish (US)
Title of host publicationAlgorithms and Computation - 8th International Symposium, ISAAC 1997, Proceedings
EditorsHon Wai Leong, Sanjay Jain, Hiroshi Imai
PublisherSpringer Verlag
Pages364-373
Number of pages10
ISBN (Print)3540638903, 9783540638902
DOIs
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)
Volume1350
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other8th Annual International Symposium on Algorithms and Computation, ISAAC 1997
CountrySingapore
CitySingapore
Period12/17/9712/19/97

Fingerprint

Maximum Matching
Cavity
Count
Vertex of a graph
Denote
Computing
Computational Biology
Tree Algorithms
Matching Problem
Optimal Algorithm
Absolute value
Shortest path
Bipartite Graph
Time Complexity
Linear Time
Upper bound
Integer
Graph in graph theory

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Kao, M. Y., Lam, T. W., Sung, W. K., & Ting, H. F. (1997). All-cavity maximum matchings. In H. W. Leong, S. Jain, & H. Imai (Eds.), Algorithms and Computation - 8th International Symposium, ISAAC 1997, Proceedings (pp. 364-373). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1350). Springer Verlag. https://doi.org/10.1007/3-540-63890-3_39
Kao, Ming Yang ; Lam, Tak Wah ; Sung, Wing Kin ; Ting, Hing Fung. / All-cavity maximum matchings. Algorithms and Computation - 8th International Symposium, ISAAC 1997, Proceedings. editor / Hon Wai Leong ; Sanjay Jain ; Hiroshi Imai. Springer Verlag, 1997. pp. 364-373 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{1b4f9612c2734b5d9794fe5d7f317105,
title = "All-cavity maximum matchings",
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.",
author = "Kao, {Ming Yang} and Lam, {Tak Wah} and Sung, {Wing Kin} and Ting, {Hing Fung}",
year = "1997",
month = "1",
day = "1",
doi = "10.1007/3-540-63890-3_39",
language = "English (US)",
isbn = "3540638903",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "364--373",
editor = "Leong, {Hon Wai} and Sanjay Jain and Hiroshi Imai",
booktitle = "Algorithms and Computation - 8th International Symposium, ISAAC 1997, Proceedings",
address = "Germany",

}

Kao, MY, Lam, TW, Sung, WK & Ting, HF 1997, All-cavity maximum matchings. in HW Leong, S Jain & H Imai (eds), Algorithms and Computation - 8th International Symposium, ISAAC 1997, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1350, Springer Verlag, pp. 364-373, 8th Annual International Symposium on Algorithms and Computation, ISAAC 1997, Singapore, Singapore, 12/17/97. https://doi.org/10.1007/3-540-63890-3_39

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 proceedingConference 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 -

Kao MY, Lam TW, Sung WK, Ting HF. All-cavity maximum matchings. In Leong HW, Jain S, Imai H, editors, Algorithms and Computation - 8th International Symposium, ISAAC 1997, Proceedings. Springer Verlag. 1997. p. 364-373. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-63890-3_39