Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings

Zhi-Zhong Chen; Ying Fan; Lusheng Wang

doi:10.1007/978-3-319-03780-6_1

Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings

Zhi-Zhong Chen, Ying Fan, Lusheng Wang

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

1 Citation (Scopus)

Abstract

We first present a fixed-parameter algorithm for the NP-hard problem of deciding if there are two matchings M₁ and M₂ in a given graph G such that |M₁| + |M₂| is no less than a given number k. The algorithm runs in O (m + k · k! · (2√2)^k · n² log n) time, where n (respectively, m) is the number of vertices (respectively, edges) in G. We then present a combinatorial approximation algorithm for the NP-hard problem of finding two disjoint matchings in a given edge-weighted graph G so that their total weight is maximized. The algorithm achieves an approximation ratio of roughly 0.76 and runs in O (m + n³ α(n)) time, where α is the inverse Ackermann function.

Original language	English
Title of host publication	Combinatorial Optimization and Applications
Subtitle of host publication	7th International Conference, COCOA 2013, Proceedings
Editors	Peter Widmayer, Yinfeng Xu, Binhai Zhu
Publisher	Springer Verlag
Pages	1-12
ISBN (Print)	9783319037790
DOIs	https://doi.org/10.1007/978-3-319-03780-6_1
Publication status	Published - Dec 2013
Event	7th International Conference on Combinatorial Optimization and Applications (COCOA 2013) - Chengdu, China Duration: 12 Dec 2013 → 14 Dec 2013 http://webdocs.cs.ualberta.ca/~ghlin/COCOA2013/

Publication series

Name	Lecture Notes in Computer Science
Volume	8287
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	7th International Conference on Combinatorial Optimization and Applications (COCOA 2013)
Country/Territory	China
City	Chengdu
Period	12/12/13 → 14/12/13
Internet address	http://webdocs.cs.ualberta.ca/~ghlin/COCOA2013/

Research Keywords

Approximation algorithms
Fixed-parameter algorithms
Graph algorithms
Matchings
NP-hardness

Access Output

10.1007/978-3-319-03780-6_1

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Chen, Z.-Z., Fan, Y., & Wang, L. (2013). Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings. In P. Widmayer, Y. Xu, & B. Zhu (Eds.), Combinatorial Optimization and Applications: 7th International Conference, COCOA 2013, Proceedings (pp. 1-12). (Lecture Notes in Computer Science; Vol. 8287). Springer Verlag. https://doi.org/10.1007/978-3-319-03780-6_1

@inproceedings{0999be2b07334776b56fd955232cdf16,

title = "Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings",

abstract = "We first present a fixed-parameter algorithm for the NP-hard problem of deciding if there are two matchings M1 and M2 in a given graph G such that |M1| + |M2| is no less than a given number k. The algorithm runs in O (m + k · k! · (2√2)k · n2 log n) time, where n (respectively, m) is the number of vertices (respectively, edges) in G. We then present a combinatorial approximation algorithm for the NP-hard problem of finding two disjoint matchings in a given edge-weighted graph G so that their total weight is maximized. The algorithm achieves an approximation ratio of roughly 0.76 and runs in O (m + n3 α(n)) time, where α is the inverse Ackermann function.",

keywords = "Approximation algorithms, Fixed-parameter algorithms, Graph algorithms, Matchings, NP-hardness",

author = "Zhi-Zhong Chen and Ying Fan and Lusheng Wang",

year = "2013",

month = dec,

doi = "10.1007/978-3-319-03780-6_1",

language = "English",

isbn = "9783319037790",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

pages = "1--12",

editor = "Peter Widmayer and Yinfeng Xu and Binhai Zhu",

booktitle = "Combinatorial Optimization and Applications",

address = "Germany",

note = "7th International Conference on Combinatorial Optimization and Applications (COCOA 2013) ; Conference date: 12-12-2013 Through 14-12-2013",

url = "http://webdocs.cs.ualberta.ca/~ghlin/COCOA2013/",

}

Chen, Z-Z, Fan, Y & Wang, L 2013, Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings. in P Widmayer, Y Xu & B Zhu (eds), Combinatorial Optimization and Applications: 7th International Conference, COCOA 2013, Proceedings. Lecture Notes in Computer Science, vol. 8287, Springer Verlag, pp. 1-12, 7th International Conference on Combinatorial Optimization and Applications (COCOA 2013), Chengdu, China, 12/12/13. https://doi.org/10.1007/978-3-319-03780-6_1

Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings. / Chen, Zhi-Zhong; Fan, Ying; Wang, Lusheng.
Combinatorial Optimization and Applications: 7th International Conference, COCOA 2013, Proceedings. ed. / Peter Widmayer; Yinfeng Xu; Binhai Zhu. Springer Verlag, 2013. p. 1-12 (Lecture Notes in Computer Science; Vol. 8287).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings

AU - Chen, Zhi-Zhong

AU - Fan, Ying

AU - Wang, Lusheng

PY - 2013/12

Y1 - 2013/12

N2 - We first present a fixed-parameter algorithm for the NP-hard problem of deciding if there are two matchings M1 and M2 in a given graph G such that |M1| + |M2| is no less than a given number k. The algorithm runs in O (m + k · k! · (2√2)k · n2 log n) time, where n (respectively, m) is the number of vertices (respectively, edges) in G. We then present a combinatorial approximation algorithm for the NP-hard problem of finding two disjoint matchings in a given edge-weighted graph G so that their total weight is maximized. The algorithm achieves an approximation ratio of roughly 0.76 and runs in O (m + n3 α(n)) time, where α is the inverse Ackermann function.

AB - We first present a fixed-parameter algorithm for the NP-hard problem of deciding if there are two matchings M1 and M2 in a given graph G such that |M1| + |M2| is no less than a given number k. The algorithm runs in O (m + k · k! · (2√2)k · n2 log n) time, where n (respectively, m) is the number of vertices (respectively, edges) in G. We then present a combinatorial approximation algorithm for the NP-hard problem of finding two disjoint matchings in a given edge-weighted graph G so that their total weight is maximized. The algorithm achieves an approximation ratio of roughly 0.76 and runs in O (m + n3 α(n)) time, where α is the inverse Ackermann function.

KW - Approximation algorithms

KW - Fixed-parameter algorithms

KW - Graph algorithms

KW - Matchings

KW - NP-hardness

UR - http://www.scopus.com/inward/record.url?scp=84893144156&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84893144156&origin=recordpage

U2 - 10.1007/978-3-319-03780-6_1

DO - 10.1007/978-3-319-03780-6_1

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783319037790

T3 - Lecture Notes in Computer Science

SP - 1

EP - 12

BT - Combinatorial Optimization and Applications

A2 - Widmayer, Peter

A2 - Xu, Yinfeng

A2 - Zhu, Binhai

PB - Springer Verlag

T2 - 7th International Conference on Combinatorial Optimization and Applications (COCOA 2013)

Y2 - 12 December 2013 through 14 December 2013

ER -

Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this