311 |
Vybrané problémy ochrany spotřebitele / Chosen problems of consumer protectionŠTEFLÍČKOVÁ, Veronika January 2009 (has links)
The main objective of diploma work was to determine consumers' awareness of their rights in the field of catering services in the Central Region in the Czech Republic. Another task was to detect the critical areas which have the greatest difficulty to respondents. As part of the questionnaire survey, which took place in November 2008 in the Central Region were asked 97 respondents.
|
312 |
Power Issues in SoCs : Power Aware DFT Architecture and Power EstimationTudu, Jaynarayan Thakurdas January 2016 (has links) (PDF)
Test power, data volume, and test time have been long-standing problems for sequential scan based testing of system-on-chip (SoC) design. The modern SoCs fabricated at lower technology nodes are complex in nature, the transistor count is as large as billions of gate for some of the microprocessors. The design complexity is further projected to increase in the coming years in accordance with Moore's law. The larger gate count and integration of multiple functionalities are the causes for higher test power dissipation, test time and data volume. The dynamic power dissipation during scan testing, i.e. during scan shift, launch and response capture, are major concerns for reliable as well as cost effective testing. Excessive average power dissipation leads to a thermal problem which causes burn-out of the chip during testing. Peak power on other hand causes test failure due to power induced additional delay. The test failure has direct impact on yield. The test power problem in modern 3D stacked based IC is even a more serious issue. Estimating the worst case functional power dissipation is yet another great challenge. The worst case functional power estimation is necessary because it gives an upper bound on the functional power dissipation which can further be used to determine the safe power zone for the test.
Several solutions in the past have been proposed to address these issues. In this thesis we have three major contributions: 1) Sequential scan chain reordering, and 2) JScan-an alternative Joint-scan DFT architecture to address primarily the test power issues along with test time and data volume, and 3) an integer linear programming methodology to address the power estimation problem. In order to reduce test power during shift, we have proposed a graph theoretic formulation for scan chain reordering and for optimum scan shift operation. For each formulation a set of algorithms is proposed. The experimental results on ISCAS-89 benchmark circuit show a reduction of around 25% and 15% in peak power and scan shift time respectively.
In order to have a holistic DFT architecture which could solve test power, test time, and data volume problems, a new DFT architecture called Joint-scan (JScan) have been developed. In JScan we have integrated the serial and random access scan architectures in a systematic way by which the JScan could harness the respective advantages from each of the architectures. The serial scan architecture
from test power, test time, and data volume problems. However, the serial scan is simple in terms of its functionality and is cost effective in terms of DFT circuitry. Whereas, the random ac-cess scan architecture is opposite to this; it is power efficient and it takes lesser time and data volume compared to serial scan. However, the random access scan occupies larger DFT area and introduces routing congestion. Therefore, we have proposed a methodology to realize the JScan architecture as an efficient alternative for standard serial and random access scan. Further, the JScan architecture is optimized and it resulted into a 2-Mode 2M-Jscan Joint-scan architecture. The proposed architectures are experimentally verified on larger benchmark circuits and compared with existing state of the art DFT architectures. The results show a reduction of 50% to 80% in test power and 30% to 50% in test time and data volume. The proposed architectures are also evaluated for routing area minimization and we obtained a saving of around 7% to 15% of chip area.
Estimating the worst case functional power being a challenging problem, we have proposed a binary integer linear programming (BILP) based methodology. Two different formulations have been proposed considering the different delay models namely zero-delay and unit-delay. The proposed methodology generates a pair or input vectors which could toggle the circuit to dissipate worst power. The BILP problems are solved using CPLEX solver for ISCAS-85 combinational benchmark circuits. For some of the circuits, the proposed methodology provided the worst possible power dissipation i.e. 80 to 100% toggling in nets.
|
313 |
Pohon sériovým zapojením rotačních hydromotorů / Drive system by serial connection of rotary hydromotorsPokorný, Pavel January 2017 (has links)
The thesis deals with the problem of large-capacity manipulation of large forgings with forging manipulator. It describes current techniques, their characteristics, advantages and disadvantages. Based on the analysis of these techniques, the thesis introduces design of the connection of the hydraulic circuit for the drive of the traveling traction wheels of the forging manipulator QKK 100 by ŽĎAS a.s. focusing on simplicity, trouble-free operation, efficiency, economy, change of speed and torque, and possibility of modification according to the current load.
|
314 |
Exploring the Frustrated Spin-Chain Compound Linarite by NMR and Thermodynamic InvestigationsSchäpers, Markus 07 October 2014 (has links)
Within the last decades low-dimensional frustrated quantum spin systems have attracted great interest in the field of modern research. In these systems a competition of various magnetic interactions takes place, leading to an energetically degenerated magnetic ground state, and thus to the occurrence of exotic, unconventional physical properties at low temperatures.
This thesis focuses on the quasi one-dimensional frustrated spin chain system linarite, PbCuSO4(OH)2. In this compound the basic building blocks are CuO4 plaquettes which are connected to each other along one crystallographic direction, analogue to a chain. The frustration in linarite is established due to the competition between the magnetic interactions. The nearest-neighbor magnetic spins are coupled ferromagnetically along the chain via a coupling constant J1, while the next-nearest neighbors are coupled antiferromagnetically via a coupling constant J2. For this configuration it is not possible to satisfy all magnetic couplings simultaneously, hence the system is magnetically frustrated.
In this work, comprehensive thermodynamic and nuclear magnetic resonance (NMR) studies demonstrate that linarite is one of the richest and most fascinating compounds in the class of low-dimensional frustrated magnets. By means of susceptibility, magnetization, specific heat, magnetocaloric effect, magnetostriction, and thermal-expansion measurements a rich magnetic phase diagram could be mapped out below a temperature of 2.8 K. The phase diagram contains five different magnetic regions/phases for an external magnetic field pointing along the chain direction. Based on the thermodynamic studies it was possible to calculate the exchange integrals within the frustrated J1-J2 model and extensions of it by using various theoretical approaches.
The magnetic microscopic nature of the different long-range magnetic phases present in linarite were investigated by NMR measurements and by collaborative neutron scattering experiments. The ground state (phase I) is identified as an incommensurate elliptical helical structure. Via a theoretical modelling the 1H-NMR spectrum of the ground state could be explained, revealing a rearrangement of the zero-field structure in an external magnetic field of 2.0 T used for the NMR studies. By further increasing the external field the system undergoes a complex spin flop transition in two steps (phase I - phase III - phase IV). In phase III a phase separation takes place where one part of the spins form a circular spiral structure while the remaining fraction form a simple antiferromagnetic structure. In phase IV the remaining circular spiral structure vanishes, so that all spins collectively form the antiferromagnetic collinear phase. The most peculiar physical properties studied in this thesis take place in region V at high fields, showing only tiny features in the thermodynamic properties. The magnetic spins in region V form a sine-wave modulated spin-density structure as identified via NMR and neutron investigations. It is discussed whether region V is related to a multipolar phase or if the spin-density wave structure could possibly coexist with such a phase.
|
315 |
In Situ and Ex Situ Investigations of Transition Metal-Catalyzed Crystallization of Carbon and Silicon Thin FilmsWenisch, Robert 29 October 2018 (has links)
Transition metal interface effects of on the crystallization of carbon and silicon were investigated. The graphitization of carbon was studied by ion beam sputter deposition of atomic carbon onto a nickel surface at temperatures ranging from room temperature to 550 °C. The resulting films were characterized by X-ray photoelectron spectroscopy, nuclear reaction analysis combined with Rutherford backscattering spectrometry, Raman spectroscopy and transmission electron microscopy. A temperature-induced and a nickel-induced effect on the graphitic ordering is demonstrated. The carbon films showed a two layered structure: directly on the nickel surface up to 8 monolayers of graphitic carbon, further deposited carbon formed less ordered structures, preferably perpendicular to the surface. The results are discussed on the basis of hyperthermal atom deposition, surface diffusion, metal-induced crystallization and dissolution-precipitation. The analysis points to a dominating role of surface diffusion-assisted crystallization in the carbon ordering process.
The kinetics of silver-induced crystallization of amorphous silicon were studied in a series of isothermal annealing experiments at 350 °C, 400 °C, 450 °C and 500 °C. The annealing process was monitored in situ employing Raman spectroscopy and Rutherford backscattering spectrometry from which time resolved information on the phase transformation and hence the kinetics are obtained. The grain structure of the crystallized silicon film was investigated with optical and scanning electron microscopy which reveals grain diameters of 5 to 8 µm. The small scale crystallinity was measured with X-ray diffraction and crystal domain sizes from 20 to 50 nm were observed. The phase transformation kinetics are discussed based on the Johnson-Mehl-Avrami-Kolmogorov theory. The analysis points to a two-dimensional, diffusion limited process with fast Avrami-type nucleation and an activation energy of 0.8 eV/at.:Contents
1. Introduction
2. Metal-Induced Crystallization
2.1. Introduction and State of the Art of Metal-Induced Crystalliza-tion
2.2. Thermodynamics of Metal-Induced Crystallization
2.3. Kinetics of Metal-Induced Crystallization
3. Ion Beam Analysis
3.1. Rutherford Backscattering Spectrometry
3.2. Nuclear Reaction Analysis
4. Raman Spectroscopy
4.1. Light Scattering in Solids
4.2. Theory
4.2.1. The Raman Spectrum of Graphitic Carbon
4.2.2. The Silicon Raman Spectrum
5. The Cluster Tool at the Ion Beam Center
5.1. General Concept
5.2. Sputtering Chamber
5.3. The Environmental Chamber
5.4. The Analysis Chamber
5.5. The Ion Beam Analysis Chamber
5.5.1. The Experimental Setup
6. The Carbon Nickel System
6.1. Experimental Details
6.1.1. Film growth
6.1.2. Characterization
6.2. Results
6.3. Discussion
7. The Silicon Silver System
7.1. Experimental
7.1.1. Film Preparation
7.1.2. In Situ Raman Spectroscopy
7.1.3. In Situ Rutherford Backscattering Spectrometry
7.2. Results
7.2.1. Raman Spectroscopy
7.2.2. Rutherford Backscattering Spectrometry
7.2.3. X-ray Diffraction
7.2.4. Optical and Scanning Electron Microscopy
7.3. Discussion
8. Conclusion and Outlook
A. Appendix
A.1. Spectroscopic Lineshapes
A.1.1. The Lorentzian Lineshape
A.1.2. The Breit-Wigner-Fano Lineshape
A.1.3. The Doniach-Sunjic Lineshape
A.1.4. The Gaussian Lineshape
A.1.5. The Voigt Lineshape
A.2. Statistcial Distribution Functions
A.2.1. The Gamma Distribution
Bibliography / Der Einfluss von Übergangsmetallkontaktflächen auf die Kristallisation von Kohlenstoff und Silizium wurde untersucht. Dazu wurde Kohlenstoff bei Temperaturen von Raumtemperatur bis 550 °C auf Nickel mittels Ionenstrahl-Sputtern abgeschieden. Die so erzeugten Filme wurden mit Röntgenphotoelektronen Spektroskopie, Kernreaktionsanalyse kombiniert mit Rutherford Rückstreu Spektrometrie, Raman Spektroskopie und Transmissions-Elektronenmikroskopie charakterisiert. Ein Nickel- und ein Temperatureffekt auf den Graphitisierungsprozess wird nachgewiesen. Die Kohlenstofffilme zeigten einen zweilagigen Aufbau: Direkt auf der Nickeloberfläche bis zu 8 Monolagen graphitischen Kohlenstoffs, weiterer abgeschiedener Kohlenstoff bildet weniger geordnete Strukturen, die bevorzugt senkrecht zur Oberfläche ausgerichtet sind. Die Ergebnisse werden auf Basis von hyperthermischer, atomarer Abscheidung, Oberflächendiffusion, Metall-induzierte Kristallisation und Lösung-Ausfällung diskutiert. Die Analysen deuten auf eine dominante Rolle der Oberflächendiffusion im Graphitisierungsprozess hin.
Die Kinetik der Silber-induzierten Kristallisation von amorphen Silizium wurde in einer Reihe von isothermalen Temperexperimenten bei 350 °C, 400 °C, 450 °C und 500 °C untersucht. Der Tempervorgang wurde mit in situ Raman Spektroskopie und in situ Rutherford Rückstreu Spektrometrie charakterisiert, wodurch zeitaufgelöste Information über den Phasenübergang und damit die Kinetik gewonnen wurden. Das Gefüge der entstandenen Siliziumschichten wurde mit optischer und Rasterelektronenmikroskopie untersucht, welche Korndurchmesser von 5 bis 8 µm zeigten. Die Kristallinität wurde mit Röntgendiffraktometrie analysiert. Hierdurch wurden Kristallitgrößen von 20 bis 50 nm bestimmt. Die Kinetik des Phasenüberganges wird anhand der Johnson-Mehl-Avrami-Kolmogorov Theorie diskutiert. Dies deutet auf einen zeidimensionalen, diffusionslimitierten Prozess mit schnell abklingender Avrami-Keimbildung hin. Die Aktivierungsenergie wurde zu 0.8 eV/At. bestimmt.:Contents
1. Introduction
2. Metal-Induced Crystallization
2.1. Introduction and State of the Art of Metal-Induced Crystalliza-tion
2.2. Thermodynamics of Metal-Induced Crystallization
2.3. Kinetics of Metal-Induced Crystallization
3. Ion Beam Analysis
3.1. Rutherford Backscattering Spectrometry
3.2. Nuclear Reaction Analysis
4. Raman Spectroscopy
4.1. Light Scattering in Solids
4.2. Theory
4.2.1. The Raman Spectrum of Graphitic Carbon
4.2.2. The Silicon Raman Spectrum
5. The Cluster Tool at the Ion Beam Center
5.1. General Concept
5.2. Sputtering Chamber
5.3. The Environmental Chamber
5.4. The Analysis Chamber
5.5. The Ion Beam Analysis Chamber
5.5.1. The Experimental Setup
6. The Carbon Nickel System
6.1. Experimental Details
6.1.1. Film growth
6.1.2. Characterization
6.2. Results
6.3. Discussion
7. The Silicon Silver System
7.1. Experimental
7.1.1. Film Preparation
7.1.2. In Situ Raman Spectroscopy
7.1.3. In Situ Rutherford Backscattering Spectrometry
7.2. Results
7.2.1. Raman Spectroscopy
7.2.2. Rutherford Backscattering Spectrometry
7.2.3. X-ray Diffraction
7.2.4. Optical and Scanning Electron Microscopy
7.3. Discussion
8. Conclusion and Outlook
A. Appendix
A.1. Spectroscopic Lineshapes
A.1.1. The Lorentzian Lineshape
A.1.2. The Breit-Wigner-Fano Lineshape
A.1.3. The Doniach-Sunjic Lineshape
A.1.4. The Gaussian Lineshape
A.1.5. The Voigt Lineshape
A.2. Statistcial Distribution Functions
A.2.1. The Gamma Distribution
Bibliography
|
316 |
DEVELOPMENT OF THERMALLY CONTROLLED LANGMUIR–SCHAEFER CONVERSION TECHNIQUES FOR SUB-10-NM HIERARCHICAL PATTERNING ACROSS MACROSCOPIC SURFACE AREASTyler R Hayes (9754796) 14 December 2020 (has links)
<div> As hybrid 2D materials are incorporated into next-generation device designs, it becomes more and more pertinent that methods are being developed which can facilitate large-area structural control of noncovalent monolayers assembled at 2D material interfaces. Noncovalent functionalization is often leveraged to modulate the physical properties of the underlying 2D material without disrupting the extended electronic delocalization networks intrinsic to its basal plane. The bottom-up nanofabrication technique of self-assembly permits sub-10-nm chemical patterning with low operational costs and relatively simple experimental designs.</div><div> The Claridge Group is interested in leveraging the unique chemical orthogonality intrinsic to the cellular membrane as a means of creating sub-10-nm hydrophilic-hydrophobic striped patterns across 2D material interfaces for applications ranging from interfacial wetting to large-area molecular templates to guide heterogeneous nanoparticle assembly. Using Langmuir–Schaefer conversion, standing phases of polymerizable amphiphiles at the air-water interfaces of a Langmuir trough are converted (through rotation) to lying-down phases on 2D material substrates. Using room temperature substrates, transfer of amphiphiles to a lowered substrate results in small domains and incomplete surface coverage.</div><div> Recognizing that heating the substrate during the LS conversion process may lower the energy barriers to molecular reorientation, and promote better molecular domain assembly, we developed a thermally controlled heated transfer stage that can maintain the surface temperature of the substrate throughout the deposition process. We found that heating during transfer results in the assembly of domains with edge lengths routinely an order of magnitude larger than transfer using room temperature substrates that are more stable towards rigorous repeat washing cycles with both polar and nonpolar solvents.</div><div> To promote the effectiveness of the LS conversion technique beyond academic environments for the noncovalent functionalization 2D material substrates for next-generation device designs, we designed and built a thermally controlled rotary stage to address the longstanding scaling demerit of LS conversion. First, we report the development of a flexible HOPG substrate film that can wrap around the perimeter of the heated disk and can be continuously cycled through the Langmuir film. We found that thermally controlled rotary (TCR) LS conversion can achieve nearly complete surface coverage at the slowest translation speed tested (0.14 mm/s). TCR–LS facilitates the assembly of domains nearly 10,000 μm<sup>2</sup> which were subsequently used as molecular templates to guide the assembly of ultranarrow AuNWs from solution in a non-heated rotary transfer step. Together, these findings provide the foundation for the use of roll-to-roll protocols to leverage LS conversion for noncovalent functionalization of 2D materials. A true roll-to-roll thermally controlled LS conversion system may prove to be advantageous and a cost-efficient process in applications that require large areas of functional surface, or benefit from long-range ordering within the functional film.</div>
|
317 |
[pt] SENSIBILIDADE DA PRÓXIMA GERAÇÃO DE DETECTORES DE NEUTRINO À OBSERVAÇÃO DOS EFEITOS DA MATÉRIA DA TERRA EM NEUTRINOS QUE VEM DE SUPERNOVAS NO CONTEXTO DO DECAIMIENTO INVISÍVEL DE NEUTRINOS / [en] SENSITIVITY OF NEXT-GENERATION NEUTRINO DETECTORS TO THE OBSERVATION OF EARTH MATTER EFFECTS ON SUPERNOVA NEUTRINOS IN THE FRAMEWORK OF INVISIBLE NEUTRINO DECAYEDWIN ALEXANDER DELGADO INSUASTY 25 January 2022 (has links)
[pt] Nesta tese estudamos o potencial que terão a próxima geração de detectores de neutrinos (JUNO, Hyper-Kamiokande e DUNE) para a detecção dos efeitos da matéria da Terra através da identificação das modulações no espectro de energia dos neutrinos de supernovas de colapso de núcleo em nossa galáxia,
assumindo a possibilidade do decaimiento invisível de v2 após os neutrinos terem deixado a estrela, caminho da Terra. Simulações recentes do colapso gravitacional (e subsequente explosão) de estrelas com massa maior do que ~ 8Mo mostram que durante a fase de esfriamento as energias médias (Eve) e
(Evx) tornam-se muito semelhantes e os fluxos tendem a se igualar, tornando difícil observar os efeitos da matéria da Terra usando um único detector. Neste trabalho mostramos que a inclusão do decaimiento dos neutrinos também cria a possibilidade de observar os efeitos em consideração no canal de detecção de
neutrinos se o ordenamento de massa for normal e no canal anti-neutrino se o ordenamento for invertido, o que não é esperado na ausência de decaimento. Em particular, se a taxa de decaimento for maior do que ~ 70%, descobrimos que o decaimento invisível de v2 pode aumentar as possibilidades de observação
dos efeitos da matéria da Terra, mesmo para supernovas a uma distância de 10 kpc de nós. / [en] In this thesis we studied the potential that the next-generation neutrino detectors (JUNO, Hyper-Kamiokande and DUNE) will have to the detection of the Earth matter effects through the identification of the modulations in the energy spectrum of neutrinos from core-collapse supernovae in our galaxy,
assuming the possibility of the invisible decay of v2 after the neutrinos have left the star, on their way to Earth. Recent simulations of gravitational collapse (and subsequent explosion) of stars more massive than ~ 8Mo show that during the cooling phase the average energies (EVe) and (Evx) become very
similar and the fluxes tend to equalize, making it difficult to observe the Earth matter effects using a single detector. In this work we show that the inclusion of neutrino decay creates also the possibility of observing the effects under consideration in the neutrino detection channel if the mass ordering is
normal and in the anti-neutrino channel if the ordering is inverted, which is not expected in the absence of neutrino decay. In particular, if the decay rate is more than ~ 70%, we find that the invisible neutrino decay of v2 can enhance the observation possibilities of Earth matter effects even for supernovae at a
distance of 10 kpc from us.
|
318 |
Algorithms for the Maximum Independent Set ProblemLê, 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.
|
319 |
Slovotvorba v německo-českém slovníku / Word Formation in German-Czech DictionaryŠemelík, Martin January 2014 (has links)
The present thesis is based on my experience as one of the contributors to The Large Academic Dictionary German-Czech. It attempts to discuss the role of word formation in German-Czech dictionaries in that it focuses on presentation of word formation in outer texts, macrostructural ordering procedures, treatment of word forming elements, special word formation parts of dictionary entries and possibilities of typography as a means word formation description in a bilingual dictionary. The approach taken is both contemplative and transformative. The thesis rests on the study of existing German-Czech dictionaries published mostly after 1945, partly between 1802 and 1945 as well. Concrete function-based proposals centred on the supposed target users of the LADGC are discussed here. A considerable part of the thesis deals with German derived nouns in Ge-...(-e) seen from a corpus linguistic view.
|
320 |
Algorithms for the Maximum Independent Set ProblemLê, 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.0508 seconds