About: Maximum cardinality matching

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Maximum cardinality matching is a fundamental problem in graph theory.We are given a graph G, and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.

Property Value
dbo:abstract
  • Maximum cardinality matching is a fundamental problem in graph theory.We are given a graph G, and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible. An important special case of the maximum cardinality matching problem is when G is a bipartite graph, whose vertices V are partitioned between left vertices in X and right vertices in Y, and edges in E always connect a left vertex to a right vertex. In this case, the problem can be efficiently solved with simpler algorithms than in the general case. (en)
dbo:wikiPageID
  • 5989592 (xsd:integer)
dbo:wikiPageLength
  • 10154 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1114776194 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • Maximum cardinality matching is a fundamental problem in graph theory.We are given a graph G, and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible. (en)
rdfs:label
  • Maximum cardinality matching (en)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License