• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 99
  • 19
  • 9
  • 3
  • Tagged with
  • 130
  • 123
  • 79
  • 61
  • 61
  • 61
  • 44
  • 21
  • 19
  • 17
  • 17
  • 15
  • 14
  • 14
  • 13
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
121

Graphene engineering

Nemec, Lydia 17 July 2015 (has links)
Die besonderen Eigenschaften von Graphen ermöglichen das Design von elektronischen Bauteilen im Nanometerbereich. Graphen kann auf der Oberfläche von Siliziumkarbonat (SiC) durch das Ausdampfen von Si epitaktisch gewachsen werden. Ein detailliertes Verständnis der atomaren und elektronischen Struktur der Grenzschicht zwischen Graphen und SiC ist ein wichtiger Schritt um die Wachstumsqualität zu verbessern. Wir nutzen Dichtefunktionaltheorie um das Hybridsystem Graphen-SiC auf atomarer Ebene zu beschreiben. Experimentelle Arbeiten auf der Si Seite von SiC haben gezeigt, dass die Grenzschicht (ZLG) durch eine teilweise kovalent gebundene Kohlenstofflage wächst; darüber bildet sich die erste Graphenlage (MLG). Durch das Konstruieren eines ab initio Oberflächenphasendiagrams zeigen wir, dass sowohl ZLG als auch MLG Gleichgewichtsphasen sind. Unsere Ergebnisse implizieren, dass Temperatur- und Druckbedingungen für den selbstbegrenzenden Graphenwachstum existieren. Wir zeigen, dass sich das Doping und die Riffellung von epitaktischem Graphene durch H-Interkalation reduzieren. Im Experiment unterscheidet sich das Graphenwachstum auf der C Seite qualitativ von der Si Seite. Zu Beginn des Graphenwachstums wird eine Mischung verschiedener Oberflächenphasen beobachtet. Wir diskutieren die Stabilität dieser konkurierenden Phasen. Die atomaren Strukturen von einigen dieser Phasen, inklusive der Graphen-SiC Grenzschicht, sind nicht bekannt wodurch die theoretische Beschreibung erschwert wird. Wir präsentieren ein neues Model für die bisher unbekannte (3x3) Rekonstruktion, das Si Twist Model. Die Oberflächenenergie vom Si Twist Model und von der bekannten (2x2)c Phase schneiden sich direkt an der Grenze zur Graphitbildung. Dies erklärt die experimentell beobachtete Phasenkoexistenz zu Beginn des Graphenwachstums. Wir schlussfolgern, dass auf der C Seite der kontrollierte Graphenewachstum durch Si-reiche Oberflächenphasen blockiert wird. / Graphene with its unique properties spurred the design of nanoscale electronic devices. Graphene films grown by Si sublimation on SiC surfaces are promising material combinations for graphene applications. Understanding the atomic and electronic structure of the SiC-graphene interface, is an important step to refine the growth quality. In this work, density-functional theory is used to simulate the SiC-graphene interface on an atomistic level without empirical parameters. Experimental work has shown that on the Si face of SiC, a partially covalently bonded carbon layer, the zero-layer graphene (ZLG), grows. On top of the ZLG layer forms mono-layer graphene (MLG) as large ordered areas and then few-layer graphene. By constructing an ab initio surface phase diagram, we show that ZLG and MLG are at least near equilibrium phases. Our results imply the existence of temperature and pressure conditions for self-limiting growth of MLG key to the large-scale graphene production. H intercalation significantly reduces both the corrugation and the graphene doping. Our calculations demonstrate that unsaturated Si atoms in the ZLG influence the electronic structure of graphene. The situation on the C face of SiC is very different. The experimental growth of large areas of graphene with well defined layer thickness is difficult. At the onset of graphene formation a phase mixture of different surface phases is observed. We will address the stability of the different occuring surface phases. However, the atomic structure of some of the competing surface phases, as well as of the SiC-graphene interface, is unknown. We present a new model for the (3x3) reconstruction, the Si twist model. The surface energies of this Si twist model, the known (2x2)c adatom phase, and a graphene covered (2x2)c phase cross at the chemical potential limit of graphite, which explains the observed phase mixture. We argue that well-controlled graphene formation is hindered by Si-rich surface phases.
122

Probing plasmonic nanostructures

Werra, Julia Franziska Maria 01 December 2016 (has links)
Elektrische und magnetische Emitter können zur Erforschung unterschiedlicher plasmonischer Nanostrukturen genutzt werden. Indem wir die Änderung der Abstrahldynamik und in der Lebensdauer bestimmen, detektieren wir die photonische lokale Zustandsdichte. Diese Zustandsdichte, die eine Eigenschaft der Umgebung ist, ermöglicht uns nicht nur Rückschlüsse auf die elektronischen und andere physikalische Eigenschaften dieser zu treffen sondern auch die allgemeinen Eigenschaften der plasmonischen Nanostruktur im Bezug auf Licht-Materie Kopplung zu bestimmen. Eine starke Licht-Materie-Kopplung ist für die zukünftige Anwendung im Bereich der Quantentechnologien wichtig. Wenn Emitter hierbei mit plasmonischen Nanostrukturen koppeln, fokussieren letztere nicht nur das emittierte Lichts an der Oberfläche im Subwellenlängenbereich sondern ermöglichen durch die Feldüberhöhung an der Oberfläche auch eine starke Licht-Materie-Kopplung. In der Arbeit konzentrieren wir uns auf zwei grundlegend unterschiedliche plasmonische Systeme: zunächst untersuchen wir analytisch den Einfluss von Graphen auf elektrische und magnetische Emitter und diskutieren dann die Lebensdaueränderungen und Strahlungsdynamiken in der Nähe von Silber- und Goldnanostrukturen. Im ersten Teil der Arbeit analysieren wir den Einfluss von Graphen mit einer Bandlücke auf den Emitter und zeigen Möglichkeiten zur experimentellen Bestimmung der Bandlücke auf. Im zweiten Teil modellieren wir die Propagation elektromagnetischer Felder im dreidimensionalen Raum mit Hilfe der Diskontinuierlichen Galerkin Zeitraum Methode mit erweiterten Funktionalitäten. Diese verwenden wir sowohl zur theoretischen Modellierung des ersten dreidimensionalen Fluoreszenlebensdauerabbildungsmikroskopie mit einem einzelnen Quantenemitter als auch zur selbstkonsistent Beschreibung von Emittern in der Nähe eines Goldpentamers. Die Kombination der Studien betont die Stärke von Emittern elektrische, optische und magnetische Eigenschaften zu detektieren. / Electric and magnetic emitters can be used to probe different plasmonic nanostructures. By determining the modification of the radiation dynamics and the lifetimes, we can measure the photonic local density of states. This, being a property of the enviroment, does not only allow us to draw conclusions regarding the electronic and other physical properties of the latter but also regarding the general light-matter coupling properties of the plasmonic nanostructure. A strong light-matter coupling is important for future applications in quantum technology. If emitters couple specifically to plasmonic nanostructure, the latter do not only focus the emitted light at the sub-wavelength scale at the surface of the structure but also allow for such a strong light-matter coupling due to the field enhancement at the surface. In this work, we focus on two different basic plasmonic systems: first, we study analytically the influence of graphene on electric and magnetic emitters, and second we discuss lifetime modifications and radiation dynamics close to silver and gold nanostructures. In the first part of this work, we specifically focus on the influence of graphene exhibiting a finite band gap on the emitter. In the second part, we model the propagation of electromagnetic fields in three-dimensional space making use of the discontinuous Galerkin time-domain method with extended functionalities. This framework we apply to model the first three-dimensional scanning-probe fluorescence-lifetime imaging microscopy by use of a single quantum-emitter as well as for a self-consistent description of emitters in the proximity of a gold pentamer. The combination of these studies stress that the strength of emitters lies in the detection of electronic, optical and magnetic properties.
123

Universal Computation and Memory by Neural Switching / Universalcomputer und Speicher mittels neuronaler Schaltvorgänge

Schittler Neves, Fabio 28 October 2010 (has links)
No description available.
124

Stabilitätsuntersuchungen zu interkalierten Metallatomen in sp2-hybridisiertem Kohlenstoff mittels Elektronenstrukturrechnungen

Dick, Daniel 24 June 2022 (has links)
Graphen und Graphit als Vertreter sp2-hybridisierter Kohlenstoffmaterialien weisen sehr gute elektronische Eigenschaften auf, die sich in vielen Fällen durch Adsorption oder Interkalation von Metallatomen weiter verbessern lassen. In dieser Arbeit wird die atomare Struktur von nickelinterkaliertem Graphit sowie von nickelbesetztem Mono- und Bilagen-Graphen und deren Stabiität mittels Dichtefunktionaltheorie berechnet und untereinander verglichen. Durch Untersuchung des Einflusses der Nickelatomdichte sowie von Anzahl und Abstand der Kohlenstofflagen werden verallgemeinerte Vorhersagen für Graphitmaterialien mit Nickelinterkalation und deren Verhalten bei externen Verspannungen möglich. Abschließend wird der Einfluss der Nickelatome auf die elektronischen Eigenschaften anhand der Bandstruktur untersucht. Aufgrund zusätzliche Bänder in der Nähe der Fermienergie kann eine Verbesserung des elektrischen Transportes angenommen werden.:Abbildungsverzeichnis Tabellenverzeichnis Abkürzungsverzeichnis Symbolverzeichnis 1. Einleitung 2. Überblick zu Kohlenstoffmaterialien 2.1. Formen des Kohlenstoffs 2.2. Interkalation 2.3. Elektronische Eigenschaften 3. Dichtefunktionaltheorie 3.1. Motivation 3.2. Das Hohenberg-Kohn-Theorem 3.3. Berechnung der Elektronendichte 3.4. Abschätzung der Austausch-Korrelations-Energie 3.4.1. Lokale Dichtenäherung 3.4.2. Verallgemeinerten Gradientennäherung 4. Simulationsmethodik 4.1. Modellsystem 4.2. Software und Rechenparameter 5. Ergebnisse 5.1. Gleichgewichtspositionen 5.1.1. Nickelbesetztes Graphen 5.1.2. Interkalierte Systeme 5.1.3. Betrachtung höherer Nickeldichten 5.2. Einfluss des Lagenabstandes und Stabilitätsbetrachtungen 5.3. Elektronische Eigenschaften 5.3.1. Einfluss der geometrischen Struktur 5.3.2. Bandstruktur von nickelbesetztem Graphen 5.3.3. Bandstrukturen der interkalierten Systeme 6. Zusammenfassung und Ausblick A. Einfluss der Nickeldichte B. SCAN-Funktional und ebeneWellen C. Energielandschaften bei konstantem Lagenabstand D. Spineffekte in der Bandstruktur E. Fette Bandstruktur der weiteren Systeme Literaturverzeichnis Selbstständigkeitserklärung
125

Atomic layer deposition of Al²O³ on NF³-pre-treated graphene

Junige, Marcel, Oddoy, Tim, Yakimovab, Rositsa, Darakchievab, Vanya, Wenger, Christian, Lupinac, Grzegorz, Kitzmann, Julia, Albert, Matthias, Bartha, Johann W. 06 September 2019 (has links)
Graphene has been considered for a variety of applications including novel nanoelectronic device concepts. However, the deposition of ultra-thin high-k dielectrics on top of graphene has still been challenging due to graphene's lack of dangling bonds. The formation of large islands and leaky films has been observed resulting from a much delayed growth initiation. In order to address this issue, we tested a pre-treatment with NF³ instead of XeF² on CVD graphene as well as epitaxial graphene monolayers prior to the Atomic Layer Deposition (ALD) of Al²O³. All experiments were conducted in vacuo; i. e. the pristine graphene samples were exposed to NF³ in the same reactor immediately before applying 30 (TMA - H²O) ALD cycles and the samples were transferred between the ALD reactor and a surface analysis unit under high vacuum conditions. The ALD growth initiation was observed by in-situ real-time Spectroscopic Ellipsometry (irtSE) with a sampling rate above 1 Hz. The total amount of Al²O³ material deposited by the applied 30 ALD cycles was cross-checked by in-vacuo X-ray Photoelectron Spectroscopy (XPS). The Al²O³ morphology was determined by Atomic Force Microscopy (AFM). The presence of graphene and its defect status was examined by in-vacuo XPS and Raman Spectroscopy before and after the coating procedure, respectively.
126

Isolated Graphene Edge Nanoelectrodes: Fabrication, Selective Functionalization, and Electrochemical Sensing

Yadav, Anur 03 August 2021 (has links)
Diese Arbeit präsentiert eine einfache eine einfache, auf Photolithographie basierende Methode zur Darstellung einer isolierten Graphenkante (oder GrEdge) einer Monolage als Nanoelektrode auf einem isolierenden Substrat vorgestellt. Trotz ihrer Millimeter-Länge verhält sich die nur einen Nanometer breite GrEdge-Elektrode wie ein Nanodraht mit einem hohen Seitenverhältnis von 1000000 zu 1. Des Weiteren wird der Einsatz von elektrochemischer Modifikation (ECM) demonstriert, um die GrEdge selektiv mit Metall-Nanopartikeln und organischen Schichten nicht-kovalente oder kovalente zu funktionalisieren, wodurch die Chemie der Kante verändert werden kann. Durch die Anbringung von Metall-Nanopartikeln kann zusätzlich oberflächenverstärkte Raman-Spektroskopie (SERS) genutzt werden, um die chemische Beschaffenheit sowohl der unberührten als auch der funktionalisierten GrEdge zu charakterisieren. Die GrEdge weist sehr hohe Mass-entransportraten auf, was charakteristisch für Nanoelektroden ist. Dementsprechend wird die voltammetrische Antwort von der Kinetik des heterogenen Elektrontransfers (HET) diktiert. An der GrEdge-Elektrode werden hohe HET-Raten beobachtet: mindestens 14 cm/s für Außensphäre sonde Ferrocenmethanol (FcMeOH) mit einem quasi-Nernst'schen Verhalten und 0,06 cm/s oder höher für innere Sphäre sonde Ferricyanide ([Fe(CN)6]3-) mit einer kinetisch kontrollierten Reaktion. Nach der selektiven Modifikation der Kante mit Goldnanopartikeln erweist sich der HET als reversibel, mit einer massentransportbegrenztes Nernst‘sches Verhalten aufweisen für beide Redoxmoleküle. Darüber hinaus ermöglicht die schnelle HET-Kinetik die Detektion der reduzierten Form von Nicotinamid-Adenin-Dinukleotid (NADH) und Flavin-Adenin-Dinukleotid (FAD) mit niedrigen Ansatzpotentialen und hinunter bis zu niedrigen mikromolaren Konzentrationen. Entsprechend verbessert die vorliegende Arbeit das Verständnis der Kante von Graphen und deren Chemie. / This thesis presents a simple photolithography-based method to realize the isolated monolayer graphene edge (or GrEdge) nanoelectrode on an insulating substrate. The millimeter-long and a nanometer-wide GrEdge is found to behave like a nanowire with a high aspect ratio of 1000000-to-1. Further, the use of electrochemical modification (ECM) is demonstrated to selectively functionalize the GrEdge with metal nanoparticles and organic moieties in a non-covalent/ covalent manner to tune the chemistry of the edge. The attachment of metal nanoparticles was used to exploit surface-enhanced Raman scattering (SERS) to characterize the chemistry of both the pristine and the functionalized GrEdge. The GrEdge electrodes were found to exhibit very high mass transport rates, characteristic of nanoelectrodes. Accordingly, the voltammetric response is found to be dictated by the kinetics of heterogeneous electron transfer (HET), attributed to the nanoscale geometry and a unique diffusional profile at such electrodes. At the GrEdge electrode, high HET rates are observed: at least 14 cm/s for outer-sphere probe, ferrocenemethanol (FcMeOH) with a quasi-Nernstian behavior; and 0.06 cm/s or higher for inner-sphere probe, ferricyanide ([Fe(CN)6]3-) with a kinetically controlled response. Upon selective modification of the edge with gold nanoparticles, the HET is found to be reversible, with a mass-transport-limited Nernstian response for both probes. Furthermore, the fast HET kinetics enables the sensing of the reduced form of nicotinamide adenine dinucleotide (NADH) and flavin adenine dinucleotide (FAD) with low onset potentials and down to low micromolar concentrations. Hence, this thesis improves the understanding of the edges of graphene and their chemistry. It also realizes isolated GrEdge as a new class of nanoelectrode which forms an important basis within the fields of fundamental electrochemistry and analytical sciences.
127

Solution Synthesis and Characterization of a Long and Curved Graphene Nanoribbon with Hybrid Cove–Armchair–Gulf Edge Structures

Yang, Lin, Zheng, Wenhao, Osella, Silvio, Droste, Jörn, Komber, Hartmut, Liu, Kun, Böckmann, Steffen, Beljonne, David, Hansen, Michael Ryan, Bonn, Mischa, Wang, Hai I., Liu, Junzhi, Feng, Xinliang, Ma, Ji 22 April 2024 (has links)
Curved graphene nanoribbons (GNRs) with hybrid edge structures have recently attracted increasing attention due to their unique band structures and electronic properties as a result of their nonplanar conformation. This work reports the solution synthesis of a long and curved multi-edged GNR (cMGNR) with unprecedented cove–armchair–gulf edge structures. The synthesis involves an efficient A2B2-type Diels–Alder polymerization between a diethynyl-substituted prefused bichrysene monomer (3b) and a dicyclopenta[e,l]pyrene-5,11-dione derivative (6) followed by FeCl3-mediated Scholl oxidative cyclodehydrogenation of the obtained polyarylenes (P1). Model compounds 1a and 1b are first synthesized to examine the suitability and efficiency of the corresponding polymers for the Scholl reaction. The successful formation of cMGNR from polymer P1 bearing prefused bichrysene units is confirmed by FTIR, Raman, and solid-state NMR analyses. The cove-edge structure of the cMGNR imparts the ribbon with a unique nonplanar conformation as revealed by density functional theory (DFT) simulation, which effectively enhances its dispersibility in solution. The cMGNR has a narrow optical bandgap of 1.61 eV, as estimated from the UV–vis absorption spectrum, which is among the family of low-bandgap solution-synthesized GNRs. Moreover, the cMGNR exhibits a carrier mobility of ≈2 cm2 V−1 s−1 inferred from contact-free terahertz spectroscopy.
128

Characterization of Viral Inhibiting 2D Carbon- Based Structures Using Scanning Probe Microscopy and Raman Spectroscopy

Gholami, Mohammad Fardin 12 June 2024 (has links)
Kohlenstoff 2D-Nanoschichten wie Graphen und Graphenoxid sind vielversprechend, aber schwierig in Bezug auf multivalente Wechselwirkungen zu kontrollieren. Das Verständnis, wie neuartige Funktionalisierungsmethoden die Geometrie, Wechselwirkungen und elektronischen Eigenschaften der Graphenblätter beeinflussen, ist der Schwerpunkt dieser Arbeit. Diese Arbeit untersucht zwei Methoden zur Modifikation von 2D-Graphennanoschichten: "Graft to" und "Graft from" Techniken, unter Verwendung von „[2+1] Nitren-Cycloaddition“ und ringöffnender Polymerisation von Glycerin, zusätzlich zum Wachstum von 2D-Triazin-Kohlenstoffstrukturen. Diese modifizierten Nanoschichten wurden hinsichtlich ihrer Wechselwirkung mit dem Vesikulären Stomatitis-Virus (VSV) und ihrer Zweidimensionalität mittels Rastersondenmikroskopie und Raman-Spektroskopie untersucht. Die Studie zeigt das Potenzial funktionalisierter Graphen in der Virologie und liefert Einblicke für zukünftige Forschungen. Ergebnisse zeigten, dass funktionalisierte 2D-TRGO an VSV-Partikel bindet und flexibel genug bleibt, um auf einer flachen Glimmeroberfläche Falten zu bilden, aber sie können die Virushüllen nicht vollständig umschließen. Dies liegt an den hohen Energiekosten für das Biegen großer lateraler Dimensionen (~1-2 μm) im Vergleich zur 200 nm Länge der VSV-Partikel. Eine optimale laterale Dimension von ~300 nm für funktionalisierte 2D-TRGO-Blätter maximiert virale Wechselwirkungen, Hemmungseffizienz und Anzeichen viraler Umhüllung. Triazin, ein Schlüsselmolekül in der Funktionalisierung, kann zur Herstellung von 2D-Triazin-Strukturen im Gramm-Maßstab verwendet werden. Potenzielle Anwendungen funktionalisierter Graphene umfassen spezialisierte antivirale Therapien und die Verwendung als Plattform für antivirale Medikamente. Zudem zeigten die Ergebnisse minimale Störungen der elektronischen Struktur von Graphen durch Triazin-Funktionalisierung. / Carbon-based 2D nanosheets like graphene and graphene oxide are promising but challenging to control in terms of multivalent interactions. Understanding how novel functionalization methods affect graphene sheets' geometry, interaction specificity and electronic properties is the focus of this thesis, which is crucial for advancing the design of 2D nanomaterials. This thesis examines two novel methods for modifying 2D graphene nanosheets: "graft to" and "graft from" techniques, using [2+1] nitrene cycloaddition reactions and ring-opening multibranch polymerization of glycerol in addition to in plane growth of 2D triazine -carbon based structures. These modified nanosheets were studied for their interaction with vesicular stomatitis virus (VSV) and their two-dimensionality using scanning probe microscopy methods and Raman spectroscopy. The study highlights the potential of functionalized graphene nanosheets in virology and provides insights for future research. Results revealed that functionalized 2D TRGO binds to VSV particles and remains flexible enough to wrinkle on a flat mica interface but they cannot completely wrap the viral envelopes. This is due to the high energy cost of bending large lateral dimensions (~1-2μm) compared to the 200 nm length of VSV particles. An optimum lateral dimension of ~300 nm for functionalized 2D TRGO sheets was found to maximize viral interactions, inhibition efficiency, and signs of viral envelopment. Triazine, a key molecule in functionalization, can also be used to create 2D triazine structures on a gram scale. Functionalized graphene's potential applications include specialized antiviral therapies, such as targeted therapies exploiting multivalent interactions between viruses and cellular receptors, and using functionalized graphene as a delivery platform for antiviral drugs. Additionally, results showed minimal disturbance of graphene electronic structure via Triazine functionalization.
129

Algorithms for the Maximum Independent Set Problem

Lê, Ngoc C. 13 July 2015 (has links) (PDF)
This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs. We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in: + some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs); + some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs); + some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs. Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes. We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem. We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs. We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered. Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.
130

Algorithms for the Maximum Independent Set Problem

Lê, Ngoc C. 18 February 2015 (has links)
This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs. We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in: + some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs); + some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs); + some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs. Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes. We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem. We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs. We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered. Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.

Page generated in 0.0811 seconds