FacultiesFakultät für Mathematik und Wirtschaftswissenschaften
InstitutionsInstitut für Optimierung und Operations Research
A matching in a graph G is a set of pairwise disjoint edges of G. The matching number of G is defined as the maximum cardinality of a matching in G. In this thesis I will present several results for subgraph-restricted versions of the matching number. For a matching M in a graph G, let G(M) be the subgraph induced by the set of vertices that are incident with an edge in M. The matching M is uniquely restricted, acyclic, or induced if M is the unique perfect matching of G(M), if G(M) is acyclic, or if G(M) is 1-regular, respectively. I provide hardness results, tractable cases, characterizations, bounds, and approximation algorithms for the above restricted matching numbers.
Subject HeadingsGraphentheorie [GND]
Matching <Graphentheorie> [GND]
Graph theory [LCSH]
KeywordsMatching; Induced Matching; Acyclic Matching; Uniquely Restricted Matching
Dewey Decimal GroupDDC 510 / Mathematics
MetadataShow full item record
This could also interest you:
Wissenschaftlicher ArtikelPenso, Lucia Draque; Rautenbach, Dieter; Souza, Ueverton dos Santos (Universität Ulm, 2018)
DissertationKonrad, Marcus (Universität Ulm, 2016-08-04)One basis for autonomous driving as well as for the evolution of semi-autonomous or driver guiding assistance systems towards autonomous driving are models of the environment. Based on these models, environmental information ...
DissertationJoos, Felix ClaudiusThe thesis is divided into three parts. The first part deals with the Erdös-Posa property of cycles. The second part presents several results concerning geometric graph representations. The third part deals with results ...