h1

% IMPORTANT: The following is UTF-8 encoded.  This means that in the presence
% of non-ASCII characters, it will not work with BibTeX 0.99 or older.
% Instead, you should use an up-to-date BibTeX implementation like “bibtex8” or
% “biber”.

@PHDTHESIS{Schmidt:760372,
      author       = {Schmidt, Isabelle Gertrud},
      othercontributors = {Triesch, Eberhard and Koster, Arie Marinus},
      title        = {{V}arianten zur {M}atching {E}xtendability in {G}raphen},
      school       = {RWTH Aachen University},
      type         = {Dissertation},
      address      = {Aachen},
      reportid     = {RWTH-2019-04138},
      pages        = {1 Online-Ressource (iv, 114 Seiten) : Illustrationen},
      year         = {2019},
      note         = {Veröffentlicht auf dem Publikationsserver der RWTH Aachen
                      University; Dissertation, RWTH Aachen University, 2019},
      abstract     = {On the one hand a 1-matching or simply a matching of a
                      graph G=(V,E) is a set of pairwise non incident edges. On
                      the other hand it can be described as an edge function which
                      maps the values 0 and 1 to the edges of G such that the sum
                      of values of incident edges to each vertex is at most 1. A
                      1-matching is called perfect if the sum of incident edges in
                      each vertex equals 1. We define the size of a 1-matching as
                      the sum of values over all edgesWe say that a graph G is
                      1-matching k-extendable if every matching of size k in G
                      extends to a perfect matching of G. The extendability number
                      of G is the maximal integer k such that G is 1-matching
                      k-extendable. Describing a 1-matching as an edge function
                      yields to the more general concept of b-matchings. In
                      analogy to the 1-matching extendability we define the
                      b-matching extendability and the 2-matching extendability as
                      a special case. In this thesis we study the complexity of
                      determining the extendability number for 2- and b-matchings.
                      After a brief survey of the theory on 1-matching
                      extendability we present a result of hackfeld from 2013. He
                      proved that the extendability problem is co-NP-complete for
                      general graphs. Furthermore, we discuss a result of Zhang
                      und Zhang showing that there is a polynomial time algorithm
                      which computes the 1-matching extendability number of
                      bipartite graphs. We generalize both results for 2-and
                      b-matchings. Considering the extendability for 2-Matchings
                      it points out that different approaches seem to be natural.
                      Thus we introduce the concepts of simple, Typ A and Typ B
                      2-matching k-extendability. For these concepts we transfer a
                      basic property of 1-matching k-extendable graphs. In
                      particular, we show that a graph which is simple (resp. Typ
                      A or Typ B) k-extendable is simple (resp. Typ A or Typ B)
                      (k-1)-extendable. Moreover, we prove that for general graphs
                      the problem of determining the simple, Typ A and Typ B
                      2-matching extendability number is co-NP-complete by using
                      an analog deduction to the proof of Hackfelds result. For
                      the Typ B 2-matching extendability we obtain the same
                      statement from the following result on the b-matching
                      extendability. In particular, we generalize all results of
                      Typ B for general and bipartite graphs to the b-matching
                      extendability. We give an (alternative) algorithm which
                      determines the b-matching extendability number for bipartite
                      graphs. This procedure generalizes the result of Zhang und
                      Zhang for the 1-matching extendability number of bipartite
                      graphs.},
      cin          = {113210 / 110000},
      ddc          = {510},
      cid          = {$I:(DE-82)113210_20140620$ / $I:(DE-82)110000_20140620$},
      typ          = {PUB:(DE-HGF)11},
      doi          = {10.18154/RWTH-2019-04138},
      url          = {https://publications.rwth-aachen.de/record/760372},
}