Matchings in Graphs Variations of the Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2007-01-01

AUTHORS

Kurt Mehlhorn

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: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "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-10-01T06:57", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_351.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-73556-4_1"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

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'

Turtle is a human-readable linked data format.

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
1 sg:pub.10.1007/978-3-540-73556-4_1 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N5e14c885d7434880ba11814542753006
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 N1125c2c656e343f8838107f7f2ea8b99
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N8d258fbb15674a80b716f90a871e4cbe
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 N1ae3337e18584bfeb91da70e9ecba553
62 N2d4dfb95e7ae46a2a3931f9b5da25469
63 schema:publisher Ncce93d3f25874195bf461a1845aa47e8
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-10-01T06:57
67 schema:sdLicense https://scigraph.springernature.com/explorer/license/
68 schema:sdPublisher N2f9d8a528ac344ce9ee8607935a5c386
69 schema:url https://doi.org/10.1007/978-3-540-73556-4_1
70 sgo:license sg:explorer/license/
71 sgo:sdDataset chapters
72 rdf:type schema:Chapter
73 N0e22ad0e234d44158a4a88b20fc66a63 schema:familyName Xu
74 schema:givenName Yinfeng
75 rdf:type schema:Person
76 N1125c2c656e343f8838107f7f2ea8b99 rdf:first Nd50ef6fae6414d27a2cec7c73851155a
77 rdf:rest Nff0fe68374fa4dadb38278ce00b2826e
78 N1ae3337e18584bfeb91da70e9ecba553 schema:name doi
79 schema:value 10.1007/978-3-540-73556-4_1
80 rdf:type schema:PropertyValue
81 N2d4dfb95e7ae46a2a3931f9b5da25469 schema:name dimensions_id
82 schema:value pub.1044019902
83 rdf:type schema:PropertyValue
84 N2f9d8a528ac344ce9ee8607935a5c386 schema:name Springer Nature - SN SciGraph project
85 rdf:type schema:Organization
86 N5e14c885d7434880ba11814542753006 rdf:first sg:person.011757371347.43
87 rdf:rest rdf:nil
88 N7f2275f8f8274dc6ae0583dcb897b4be rdf:first Nf351125e940b427fafcf1d99445ee46a
89 rdf:rest rdf:nil
90 N8d258fbb15674a80b716f90a871e4cbe schema:isbn 978-3-540-73555-7
91 978-3-540-73556-4
92 schema:name Combinatorial Optimization and Applications
93 rdf:type schema:Book
94 Ncce93d3f25874195bf461a1845aa47e8 schema:name Springer Nature
95 rdf:type schema:Organisation
96 Nd50ef6fae6414d27a2cec7c73851155a schema:familyName Dress
97 schema:givenName Andreas
98 rdf:type schema:Person
99 Nf351125e940b427fafcf1d99445ee46a schema:familyName Zhu
100 schema:givenName Binhai
101 rdf:type schema:Person
102 Nff0fe68374fa4dadb38278ce00b2826e rdf:first N0e22ad0e234d44158a4a88b20fc66a63
103 rdf:rest N7f2275f8f8274dc6ae0583dcb897b4be
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
 




Preview window. Press ESC to close (or click here)


...