# Matchings in Graphs Variations of the Problem

Ontology type: schema:Chapter

### Chapter Info

DATE

2007-01-01

AUTHORS ABSTRACT

Many real-life optimization problems are naturally formulated as questions about matchings in (bipartite) graphs.We have a bipartite graph. The edge set is partitioned into classes E1, E2, . . . , Er. For a matching M, let si be the number of edges in M ∩ Ei. A rank − maximal matching maximizes the vector (s1, s2, . . . , sr). We show how to compute a rank-maximal matching in time O(r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\sqrt{nm}$\end{document}) [IKM + 06].We have a bipartite graph. The vertices on one side of the graph rank the vertices on the other side; there are no ties. We call a matching M more popular than a matching N if the number of nodes preferring M over N is larger than the number of nodes preferring N over M. We call a matching popular, if there is no matching which is more popular. We characterize the instances with a popular matching, decide the existence of a popular matching, and compute a popular matching (if one exists) in time O(\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\sqrt{nm}$\end{document}) [AIKM05].We have a bipartite graph. The vertices on both sides rank the edges incident to them with ties allowed. A matching M is stable if there is no pair \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$(a, b) \in E{\backslash}M$\end{document} such that a prefers b over her mate in M and b prefers a over his mate in M or is indifferent between a and his mate. We show how to compute stable matchings in time O(nm) [KMMP04].In a random graph, edges are present with probability p independent of other edges. We show that for p ≥ c0/n and c0 a suitable constant, every non-maximal matching has a logarithmic length augmenting path. As a consequence the average running time of matching algorithms on random graphs is O(m log n) [BMSH05]. More... »

PAGES

1-2

### Book

TITLE

Combinatorial Optimization and Applications

ISBN

978-3-540-73555-7
978-3-540-73556-4

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-73556-4_1

DOI

http://dx.doi.org/10.1007/978-3-540-73556-4_1

DIMENSIONS

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

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": "Max-Planck-Institut f\u00fcr Informatik, Stuhlsatzenhausweg 86, 66123 Saarbr\u00fccken, Germany",
"id": "http://www.grid.ac/institutes/grid.419528.3",
"name": [
"Max-Planck-Institut f\u00fcr Informatik, Stuhlsatzenhausweg 86, 66123 Saarbr\u00fccken, Germany"
],
"type": "Organization"
},
"familyName": "Mehlhorn",
"givenName": "Kurt",
"id": "sg:person.011757371347.43",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43"
],
"type": "Person"
}
],
"datePublished": "2007-01-01",
"datePublishedReg": "2007-01-01",
"description": "Many real-life optimization problems are naturally formulated as questions about matchings in (bipartite) graphs.We have a bipartite graph. The edge set is partitioned into classes E1, E2, . . . , Er. For a matching M, let si be the number of edges in M\u2009\u2229\u2009Ei. A rank\u2009\u2212\u2009maximal matching maximizes the vector (s1, s2, . . . , sr). We show how to compute a rank-maximal matching in time O(r\\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}$\\sqrt{nm}$\\end{document}) [IKM\u2009+\u200906].We have a bipartite graph. The vertices on one side of the graph rank the vertices on the other side; there are no ties. We call a matching M more popular than a matching N if the number of nodes preferring M over N is larger than the number of nodes preferring N over M. We call a matching popular, if there is no matching which is more popular. We characterize the instances with a popular matching, decide the existence of a popular matching, and compute a popular matching (if one exists) in time O(\\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}$\\sqrt{nm}$\\end{document}) [AIKM05].We have a bipartite graph. The vertices on both sides rank the edges incident to them with ties allowed. A matching M is stable if there is no pair \\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}$(a, b) \\in E{\\backslash}M$\\end{document} such that a prefers b over her mate in M and b prefers a over his mate in M or is indifferent between a and his mate. We show how to compute stable matchings in time O(nm) [KMMP04].In a random graph, edges are present with probability p independent of other edges. We show that for p \u2265 c0/n and c0 a suitable constant, every non-maximal matching has a logarithmic length augmenting path. As a consequence the average running time of matching algorithms on random graphs is O(m log n) [BMSH05].",
"editor": [
{
"familyName": "Dress",
"givenName": "Andreas",
"type": "Person"
},
{
"familyName": "Xu",
"givenName": "Yinfeng",
"type": "Person"
},
{
"familyName": "Zhu",
"givenName": "Binhai",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-540-73556-4_1",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-540-73555-7",
"978-3-540-73556-4"
],
"name": "Combinatorial Optimization and Applications",
"type": "Book"
},
"keywords": [
"random graphs",
"bipartite graphs",
"real-life optimization problems",
"number of nodes",
"number of edges",
"optimization problem",
"average running time",
"edge sets",
"maximal matching",
"logarithmic length",
"suitable constant",
"edges incident",
"running time",
"graph",
"graph variations",
"vertices",
"rank-maximal matchings",
"stable matching",
"problem",
"edge",
"popular matching",
"matching",
"algorithm",
"existence",
"number",
"nodes",
"C0",
"set",
"rank",
"vector",
"path",
"constants",
"time",
"instances",
"pairs",
"side",
"length",
"variation",
"EI",
"independent",
"incidents",
"questions",
"consequences",
"ties",
"E1",
"Popular",
"E2",
"mates"
],
"name": "Matchings in Graphs Variations of the Problem",
"pagination": "1-2",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1044019902"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-540-73556-4_1"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-540-73556-4_1",
"https://app.dimensions.ai/details/publication/pub.1044019902"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-11-24T21:16",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/chapter/chapter_35.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-540-73556-4_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-540-73556-4_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-540-73556-4_1'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-73556-4_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-540-73556-4_1'

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

117 TRIPLES      22 PREDICATES      72 URIs      65 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author N4442e02212704d8eabe4f2451fa4d36d
4 schema:datePublished 2007-01-01
5 schema:datePublishedReg 2007-01-01
6 schema:description Many real-life optimization problems are naturally formulated as questions about matchings in (bipartite) graphs.We have a bipartite graph. The edge set is partitioned into classes E1, E2, . . . , Er. For a matching M, let si be the number of edges in M ∩ Ei. A rank − maximal matching maximizes the vector (s1, s2, . . . , sr). We show how to compute a rank-maximal matching in time O(r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\sqrt{nm}$\end{document}) [IKM + 06].We have a bipartite graph. The vertices on one side of the graph rank the vertices on the other side; there are no ties. We call a matching M more popular than a matching N if the number of nodes preferring M over N is larger than the number of nodes preferring N over M. We call a matching popular, if there is no matching which is more popular. We characterize the instances with a popular matching, decide the existence of a popular matching, and compute a popular matching (if one exists) in time O(\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\sqrt{nm}$\end{document}) [AIKM05].We have a bipartite graph. The vertices on both sides rank the edges incident to them with ties allowed. A matching M is stable if there is no pair \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$(a, b) \in E{\backslash}M$\end{document} such that a prefers b over her mate in M and b prefers a over his mate in M or is indifferent between a and his mate. We show how to compute stable matchings in time O(nm) [KMMP04].In a random graph, edges are present with probability p independent of other edges. We show that for p ≥ c0/n and c0 a suitable constant, every non-maximal matching has a logarithmic length augmenting path. As a consequence the average running time of matching algorithms on random graphs is O(m log n) [BMSH05].
7 schema:editor N044404f8dee141299013d86255bd522d
8 schema:genre chapter
9 schema:isAccessibleForFree false
11 schema:keywords C0
12 E1
13 E2
14 EI
15 Popular
16 algorithm
17 average running time
18 bipartite graphs
19 consequences
20 constants
21 edge
22 edge sets
23 edges incident
24 existence
25 graph
26 graph variations
27 incidents
28 independent
29 instances
30 length
31 logarithmic length
32 matching
33 mates
34 maximal matching
35 nodes
36 number
37 number of edges
38 number of nodes
39 optimization problem
40 pairs
41 path
42 popular matching
43 problem
44 questions
45 random graphs
46 rank
47 rank-maximal matchings
48 real-life optimization problems
49 running time
50 set
51 side
52 stable matching
53 suitable constant
54 ties
55 time
56 variation
57 vector
58 vertices
59 schema:name Matchings in Graphs Variations of the Problem
60 schema:pagination 1-2
61 schema:productId N3ec518c8350c45f39c8a4f37938e7959
62 N590b9445f0d54d2dafce97fc0186dc66
63 schema:publisher Nbe415d40a45f4baebbff8b1b3f432de5
64 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044019902
65 https://doi.org/10.1007/978-3-540-73556-4_1
66 schema:sdDatePublished 2022-11-24T21:16
68 schema:sdPublisher N78eb5834dc264ef99a3c35bce98baf67
69 schema:url https://doi.org/10.1007/978-3-540-73556-4_1
71 sgo:sdDataset chapters
72 rdf:type schema:Chapter
73 N044404f8dee141299013d86255bd522d rdf:first Nb1c1714f42ec4a4da8e0ae145d4a74bc
74 rdf:rest Ndfc20afe6a38422a88fa05efc31effe4
76 978-3-540-73556-4
77 schema:name Combinatorial Optimization and Applications
78 rdf:type schema:Book
79 N39cc5597613446ef9f5a51f104249405 rdf:first N50c98a5102464253bf94d9093cab13c7
80 rdf:rest rdf:nil
81 N3ec518c8350c45f39c8a4f37938e7959 schema:name dimensions_id
82 schema:value pub.1044019902
83 rdf:type schema:PropertyValue
84 N4442e02212704d8eabe4f2451fa4d36d rdf:first sg:person.011757371347.43
85 rdf:rest rdf:nil
86 N4d9b3dc0b828405ab7aeb76e64c54503 schema:familyName Xu
87 schema:givenName Yinfeng
88 rdf:type schema:Person
89 N50c98a5102464253bf94d9093cab13c7 schema:familyName Zhu
90 schema:givenName Binhai
91 rdf:type schema:Person
92 N590b9445f0d54d2dafce97fc0186dc66 schema:name doi
93 schema:value 10.1007/978-3-540-73556-4_1
94 rdf:type schema:PropertyValue
95 N78eb5834dc264ef99a3c35bce98baf67 schema:name Springer Nature - SN SciGraph project
96 rdf:type schema:Organization
97 Nb1c1714f42ec4a4da8e0ae145d4a74bc schema:familyName Dress
98 schema:givenName Andreas
99 rdf:type schema:Person
100 Nbe415d40a45f4baebbff8b1b3f432de5 schema:name Springer Nature
101 rdf:type schema:Organisation
102 Ndfc20afe6a38422a88fa05efc31effe4 rdf:first N4d9b3dc0b828405ab7aeb76e64c54503
103 rdf:rest N39cc5597613446ef9f5a51f104249405
104 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
105 schema:name Information and Computing Sciences
106 rdf:type schema:DefinedTerm
107 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
108 schema:name Computation Theory and Mathematics
109 rdf:type schema:DefinedTerm
110 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
111 schema:familyName Mehlhorn
112 schema:givenName Kurt
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
114 rdf:type schema:Person
115 grid-institutes:grid.419528.3 schema:alternateName Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 86, 66123 Saarbrücken, Germany
116 schema:name Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 86, 66123 Saarbrücken, Germany
117 rdf:type schema:Organization