This HTML5 document contains 40 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n9http://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Maximum_cardinality_matching
rdfs:label
Maximum cardinality matching
rdfs:comment
Maximum cardinality matching is a fundamental problem in graph theory.We are given a graph , 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.
dbp:wikiPageUsesTemplate
dbt:Radical dbt:Reflist dbt:Short_description dbt:Math
dct:subject
dbc:Matching_(graph_theory) dbc:Graph_theory
prov:wasDerivedFrom
n9:Maximum_cardinality_matching?oldid=1053985579&ns=0
dbo:wikiPageID
5989592
dbo:wikiPageLength
9939
dbo:wikiPageRevisionID
1053985579
dbo:wikiPageWikiLink
dbr:Graph_theory dbr:Randomized_algorithm dbr:Matrix_multiplication dbr:Maximum_flow_problem dbr:Matching_in_hypergraphs dbr:Maximum_weight_matching dbr:Ford–Fulkerson_algorithm dbr:Glossary_of_graph_theory dbr:Blossom_algorithm dbr:Flow_network dbr:Graph_(discrete_mathematics) dbc:Graph_theory dbr:Hopcroft–Karp_algorithm dbr:Bipartite_graph dbr:Generalized_assignment_problem dbr:Harold_N._Gabow dbr:Approximation_algorithm dbr:Assignment_problem dbr:Matching_(graph_theory) dbr:Perfect_matching dbr:Norbert_Blum_(computer_scientist) dbc:Matching_(graph_theory) dbr:Dense_graph dbr:Robert_Tarjan dbr:Planar_graph dbr:Priority_matching
dbo:abstract
Maximum cardinality matching is a fundamental problem in graph theory.We are given a graph , 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.
foaf:isPrimaryTopicOf
n9:Maximum_cardinality_matching