Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings

Ontology type: schema:Chapter

Chapter Info

DATE

2013

AUTHORS 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O\left(m + k\cdot k!\cdot \left(2\sqrt{2}\right)^k\cdot n^2\log n \ \right)$\end{document} 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O\left(m + n^3\alpha(n)\right)$\end{document} time, where α is the inverse Ackermann function. More... »

PAGES

1-12

Book

TITLE

Combinatorial Optimization and Applications

ISBN

978-3-319-03779-0
978-3-319-03780-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-03780-6_1

DOI

http://dx.doi.org/10.1007/978-3-319-03780-6_1

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1040219405

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan",
"id": "http://www.grid.ac/institutes/grid.412773.4",
"name": [
"Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan"
],
"type": "Organization"
},
"familyName": "Chen",
"givenName": "Zhi-Zhong",
"id": "sg:person.015654265661.98",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR, Hong Kong",
"id": "http://www.grid.ac/institutes/grid.35030.35",
"name": [
"Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR, Hong Kong"
],
"type": "Organization"
},
"familyName": "Fan",
"givenName": "Ying",
"id": "sg:person.016605774033.37",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016605774033.37"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR, Hong Kong",
"id": "http://www.grid.ac/institutes/grid.35030.35",
"name": [
"Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR, Hong Kong"
],
"type": "Organization"
},
"familyName": "Wang",
"givenName": "Lusheng",
"id": "sg:person.01105113721.52",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52"
],
"type": "Person"
}
],
"datePublished": "2013",
"datePublishedReg": "2013-01-01",
"description": "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|\u2009+\u2009|M2| is no less than a given number k. The algorithm runs in \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O\\left(m + k\\cdot k!\\cdot \\left(2\\sqrt{2}\\right)^k\\cdot n^2\\log n \\ \\right)$\\end{document} 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 \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O\\left(m + n^3\\alpha(n)\\right)$\\end{document} time, where \u03b1 is the inverse Ackermann function.",
"editor": [
{
"familyName": "Widmayer",
"givenName": "Peter",
"type": "Person"
},
{
"familyName": "Xu",
"givenName": "Yinfeng",
"type": "Person"
},
{
"familyName": "Zhu",
"givenName": "Binhai",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-319-03780-6_1",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-319-03779-0",
"978-3-319-03780-6"
],
"name": "Combinatorial Optimization and Applications",
"type": "Book"
},
"keywords": [
"NP-hard problem",
"disjoint matchings",
"approximation algorithm",
"graph G",
"combinatorial approximation algorithm",
"edge-weighted graph G",
"number of vertices",
"inverse Ackermann function",
"fixed-parameter algorithm",
"approximation ratio",
"Ackermann function",
"algorithm",
"problem",
"vertices",
"matching",
"number",
"total weight",
"function",
"time",
"ratio",
"weight",
"M1",
"m2"
],
"name": "Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings",
"pagination": "1-12",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1040219405"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-319-03780-6_1"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-319-03780-6_1",
"https://app.dimensions.ai/details/publication/pub.1040219405"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-10T10:41",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_193.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-319-03780-6_1"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-03780-6_1'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-03780-6_1'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-03780-6_1'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-03780-6_1'

This table displays all metadata directly associated to this object as RDF triples.

110 TRIPLES      23 PREDICATES      49 URIs      42 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author N069880780a3a4a0eab0aa4027c164fa2
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O\left(m + k\cdot k!\cdot \left(2\sqrt{2}\right)^k\cdot n^2\log n \ \right)$\end{document} 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O\left(m + n^3\alpha(n)\right)$\end{document} time, where α is the inverse Ackermann function.
7 schema:editor N37eece87da9e4c1b97b43fca81cd5074
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N79b6dde07b5047fab3ccbe1f71e7345a
12 schema:keywords Ackermann function
13 M1
14 NP-hard problem
15 algorithm
16 approximation algorithm
17 approximation ratio
18 combinatorial approximation algorithm
19 disjoint matchings
20 edge-weighted graph G
21 fixed-parameter algorithm
22 function
23 graph G
24 inverse Ackermann function
25 m2
26 matching
27 number
28 number of vertices
29 problem
30 ratio
31 time
32 total weight
33 vertices
34 weight
35 schema:name Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings
36 schema:pagination 1-12
37 schema:productId N19ecfe3369ea4bcb91725fcaa0dc6296
38 Nda4cdf0952104973bc1217a6bc012409
39 schema:publisher Nff1696bf1f824647bc1c985cbce5e5d6
40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040219405
41 https://doi.org/10.1007/978-3-319-03780-6_1
42 schema:sdDatePublished 2022-05-10T10:41
44 schema:sdPublisher Nf2d258ed793347deb46bc2d524be8104
45 schema:url https://doi.org/10.1007/978-3-319-03780-6_1
47 sgo:sdDataset chapters
48 rdf:type schema:Chapter
49 N069880780a3a4a0eab0aa4027c164fa2 rdf:first sg:person.015654265661.98
50 rdf:rest N954ff32199884572b913337591cee853
51 N0e50fbbba3ae4eafb8ccf350eefa8336 rdf:first sg:person.01105113721.52
52 rdf:rest rdf:nil
53 N10aaf1f8985b4b23b1a02d4fe9eaf10a schema:familyName Widmayer
54 schema:givenName Peter
55 rdf:type schema:Person
56 N1229bca39f504bc29505cc68b640e7dc rdf:first N30e2a66ce5d244baba32ed4aedcbd539
57 rdf:rest rdf:nil
58 N19ecfe3369ea4bcb91725fcaa0dc6296 schema:name dimensions_id
59 schema:value pub.1040219405
60 rdf:type schema:PropertyValue
61 N30e2a66ce5d244baba32ed4aedcbd539 schema:familyName Zhu
62 schema:givenName Binhai
63 rdf:type schema:Person
64 N37eece87da9e4c1b97b43fca81cd5074 rdf:first N10aaf1f8985b4b23b1a02d4fe9eaf10a
67 rdf:rest N1229bca39f504bc29505cc68b640e7dc
68 N439b80bc08f04422a8066b37fe55e508 schema:familyName Xu
69 schema:givenName Yinfeng
70 rdf:type schema:Person
71 N79b6dde07b5047fab3ccbe1f71e7345a schema:isbn 978-3-319-03779-0
72 978-3-319-03780-6
73 schema:name Combinatorial Optimization and Applications
74 rdf:type schema:Book
75 N954ff32199884572b913337591cee853 rdf:first sg:person.016605774033.37
76 rdf:rest N0e50fbbba3ae4eafb8ccf350eefa8336
77 Nda4cdf0952104973bc1217a6bc012409 schema:name doi
78 schema:value 10.1007/978-3-319-03780-6_1
79 rdf:type schema:PropertyValue
80 Nf2d258ed793347deb46bc2d524be8104 schema:name Springer Nature - SN SciGraph project
81 rdf:type schema:Organization
82 Nff1696bf1f824647bc1c985cbce5e5d6 schema:name Springer Nature
83 rdf:type schema:Organisation
84 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
85 schema:name Information and Computing Sciences
86 rdf:type schema:DefinedTerm
87 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
88 schema:name Computation Theory and Mathematics
89 rdf:type schema:DefinedTerm
90 sg:person.01105113721.52 schema:affiliation grid-institutes:grid.35030.35
91 schema:familyName Wang
92 schema:givenName Lusheng
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52
94 rdf:type schema:Person
95 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
96 schema:familyName Chen
97 schema:givenName Zhi-Zhong
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
99 rdf:type schema:Person
100 sg:person.016605774033.37 schema:affiliation grid-institutes:grid.35030.35
101 schema:familyName Fan
102 schema:givenName Ying
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016605774033.37
104 rdf:type schema:Person
105 grid-institutes:grid.35030.35 schema:alternateName Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR, Hong Kong
106 schema:name Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR, Hong Kong
107 rdf:type schema:Organization
108 grid-institutes:grid.412773.4 schema:alternateName Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
109 schema:name Division of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
110 rdf:type schema:Organization