h1

h2

h3

h4

h5
h6

001     760372
005     20230408005943.0
024 7 _ |2 HBZ
|a HT020051690
024 7 _ |2 Laufende Nummer
|a 38136
024 7 _ |2 datacite_doi
|a 10.18154/RWTH-2019-04138
037 _ _ |a RWTH-2019-04138
041 _ _ |a German
082 _ _ |a 510
100 1 _ |0 P:(DE-588)1185609210
|a Schmidt, Isabelle Gertrud
|b 0
|u rwth
245 _ _ |a Varianten zur Matching Extendability in Graphen
|c vorgelegt von Diplom-Mathematikerin Isabelle Gertrud Schmidt
|h online
246 _ 3 |a Some generalizations of matching extendability in graphs
|y English
260 _ _ |a Aachen
|c 2019
300 _ _ |a 1 Online-Ressource (iv, 114 Seiten) : Illustrationen
336 7 _ |0 2
|2 EndNote
|a Thesis
336 7 _ |0 PUB:(DE-HGF)11
|2 PUB:(DE-HGF)
|a Dissertation / PhD Thesis
|b phd
|m phd
336 7 _ |2 BibTeX
|a PHDTHESIS
336 7 _ |2 DRIVER
|a doctoralThesis
336 7 _ |2 DataCite
|a Output Types/Dissertation
336 7 _ |2 ORCID
|a DISSERTATION
500 _ _ |a Veröffentlicht auf dem Publikationsserver der RWTH Aachen University
502 _ _ |a Dissertation, RWTH Aachen University, 2019
|b Dissertation
|c RWTH Aachen University
|d 2019
|g Fak01
|o 2019-04-26
520 3 _ |a Ein 1-Matching (oder einfach Matching) in einem Graph G=(V,E) kann einerseits als eine Menge unabhängiger, d.h. paarweise nicht inzidenter, Kanten definiert werden. Andererseits kann ein 1-Matching als eine Kantenfunktion beschrieben werden, die jeder Kante den Wert 0 oder 1 zuordnet unter Berücksichtigung, dass die Summe der Werte inzidenter Kanten zu einer Ecke maximal 1 sein darf. Ein 1-Matching heißt perfekt, falls die Summe der Werte inzidenter Kanten in jeder Ecke gleich 1 ist. Mit der Größe eines Matchings bezeichnen wir die Summe der Werte der Kanten des Matchings. Ist es in einem Graph G möglich, jedes 1-Matching der Größe k zu einem perfekten 1-Matching zu erweitern, so nennen wir G 1-Matching k-extendable. Für einen gegebenen Graph G bezeichnet die Extendabilityzahl von G die größte Zahl k mit der Eigenschaft, dass G 1-Matching k-extendable ist. Die Beschreibung des 1-Matchings als Kantenfunktion lässt sich zu dem allgemeinen Konzept der b-Matchings erweitern. In Analogie zu der 1-Matching Extendability definieren wir die b-Matching Extendability sowie als Spezialfall die 2-Matching Extendability. Der Schwerpunkt dieser Arbeit liegt auf den Untersuchungen zur Komplexität des Problems der Bestimmung der Extendabilityzahl für 2-Matchings und b-Matchings. Diese Probleme bezeichnen wir als 2-Matching bzw. b-Matching Extendabilityproblem. Auf Grundlage eines Überblicks über die Theorie der Extendability für 1-Matchings stellen wir ein Ergebnis von Hackfeld aus dem Jahr 2013 vor, das die co-NP-Vollständigkeit des 1-Matching Extendabilityproblems für allgemeine Graphen zeigt. Weiter diskutieren wir ausführlich ein Ergebnis von Zhang und Zhang aus dem Jahr 2006, das beweist, dass das 1-Matching Extendabilityproblem für bipartite Graphen in polynomieller Zeit lösbar ist. Diese beiden Ergebnisse verallgemeinern wir im folgenden für 2- und b-Matchings. Da bei der Betrachtung des Begriffs der Extendability auf 2-Matchings verschiedene Ansätze sinnvoll erscheinen, führen wir zunächst die Konzepte der simple, Typ A und Typ B 2-Matching k-Extendability ein. Auf diese Konzepte übertragen wir eine der grundlegenden Eigenschaften der 1-Matching Extendability; diese besagt, dass ein Graph, der k-extendable ist auch (k-1)-extendable ist. Anschließend können wir für alle Konzepte die co-NP-Vollständigkeit des 2-Matching Extendabilityproblems für allgemeine Graphen auf der Grundlage von Hackfeld nachweisen. Für den Typ B können wir zusätzlich die co-NP-Vollständigkeit aus den nachfolgenden Ergebnissen bezüglich der b-Matchings folgern. Anschließend untersuchen wir die in den vorherigen Kapiteln betrachteten Ergebnisse für b-Matchings im Sinne des Typs B auf allgemeinen und bipartiten Graphen. Dabei stellen wir einen alternativen Algorithmus zur Bestimmung der b-Matching k-Extendability für bipartite Graphen vor, der das Ergebnis von Zhang und Zhang für bipartite Graphen bezüglich 1-Matchings verallgemeinert.
|l ger
520 _ _ |a 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.
|l eng
588 _ _ |a Dataset connected to Lobid/HBZ
591 _ _ |a Germany
653 _ 7 |a 2-matching extendability
653 _ 7 |a b-matching extendability
653 _ 7 |a matching extensions
700 1 _ |0 P:(DE-82)IDM00098
|a Triesch, Eberhard
|b 1
|e Thesis advisor
|u rwth
700 1 _ |0 P:(DE-82)IDM00097
|a Koster, Arie Marinus
|b 2
|e Thesis advisor
|u rwth
856 4 _ |u https://publications.rwth-aachen.de/record/760372/files/760372.pdf
|y OpenAccess
856 4 _ |u https://publications.rwth-aachen.de/record/760372/files/760372_source.zip
|y Restricted
856 4 _ |u https://publications.rwth-aachen.de/record/760372/files/760372.gif?subformat=icon
|x icon
|y OpenAccess
856 4 _ |u https://publications.rwth-aachen.de/record/760372/files/760372.jpg?subformat=icon-1440
|x icon-1440
|y OpenAccess
856 4 _ |u https://publications.rwth-aachen.de/record/760372/files/760372.jpg?subformat=icon-180
|x icon-180
|y OpenAccess
856 4 _ |u https://publications.rwth-aachen.de/record/760372/files/760372.jpg?subformat=icon-640
|x icon-640
|y OpenAccess
856 4 _ |u https://publications.rwth-aachen.de/record/760372/files/760372.jpg?subformat=icon-700
|x icon-700
|y OpenAccess
909 C O |o oai:publications.rwth-aachen.de:760372
|p dnbdelivery
|p driver
|p VDB
|p open_access
|p openaire
910 1 _ |0 I:(DE-588b)36225-6
|6 P:(DE-588)1185609210
|a RWTH Aachen
|b 0
|k RWTH
910 1 _ |0 I:(DE-588b)36225-6
|6 P:(DE-82)IDM00098
|a RWTH Aachen
|b 1
|k RWTH
910 1 _ |0 I:(DE-588b)36225-6
|6 P:(DE-82)IDM00097
|a RWTH Aachen
|b 2
|k RWTH
914 1 _ |y 2019
915 _ _ |0 StatID:(DE-HGF)0510
|2 StatID
|a OpenAccess
920 1 _ |0 I:(DE-82)113210_20140620
|k 113210
|l Lehrstuhl II für Mathematik (für Ingenieure)
|x 0
920 1 _ |0 I:(DE-82)110000_20140620
|k 110000
|l Fachgruppe Mathematik
|x 1
980 1 _ |a FullTexts
980 _ _ |a I:(DE-82)110000_20140620
980 _ _ |a I:(DE-82)113210_20140620
980 _ _ |a UNRESTRICTED
980 _ _ |a VDB
980 _ _ |a phd

LibraryCollectionCLSMajorCLSMinorLanguageAuthor
Marc 21