- 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.
Search results
Showing 21 to 26 of 26 (0.022 seconds)| 21 |
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.
|
| 22 |
Implications of neuronal excitability and morphology for spike-based information transmissionHesse, Janina 29 November 2017 (has links)
Signalverarbeitung im Nervensystem hängt sowohl von der Netzwerkstruktur, als auch den zellulären Eigenschaften der Nervenzellen ab. In dieser Abhandlung werden zwei zelluläre Eigenschaften im Hinblick auf ihre funktionellen Anpassungsmöglichkeiten untersucht: Es wird gezeigt, dass neuronale Morphologie die Signalweiterleitung unter Berücksichtigung energetischer Beschränkungen verstärken kann, und dass selbst kleine Änderungen in biophysikalischen Parametern die Aktivierungsbifurkation in Nervenzellen, und damit deren Informationskodierung, wechseln können. Im ersten Teil dieser Abhandlung wird, unter Verwendung von mathematischen Modellen und Daten, die Hypothese aufgestellt, dass Energie-effiziente Signalweiterleitung als starker Evolutionsdruck für unterschiedliche Zellkörperlagen bei Nervenzellen wirkt. Um Energie zu sparen, kann die Signalweiterleitung vom Dendrit zum Axon verstärkt werden, indem relativ kleine Zellkörper zwischen Dendrit und Axon eingebaut werden, während relativ große Zellkörper besser ausgelagert werden. Im zweiten Teil wird gezeigt, dass biophysikalische Parameter, wie Temperatur, Membranwiderstand oder Kapazität, den Feuermechanismus des Neurons ändern, und damit gleichfalls Aktionspotential-basierte Informationsverarbeitung. Diese Arbeit identifiziert die sogenannte "saddle-node-loop" (Sattel-Knoten-Schlaufe) Bifurkation als den Übergang, der besonders drastische funktionale Auswirkungen hat. Neben der Änderung neuronaler Filtereigenschaften sowie der Ankopplung an Stimuli, führt die "saddle-node-loop" Bifurkation zu einer Erhöhung der Netzwerk-Synchronisation, was möglicherweise für das Auslösen von Anfällen durch Temperatur, wie bei Fieberkrämpfen, interessant sein könnte. / Signal processing in nervous systems is shaped by the connectome as well as the cellular properties of nerve cells. In this thesis, two cellular properties are investigated with respect to the functional adaptations they provide: It is shown that neuronal morphology can improve signal transmission under energetic constraints, and that even small changes in biophysical parameters can switch spike generation, and thus information encoding. In the first project of the thesis, mathematical modeling and data are deployed to suggest energy-efficient signaling as a major evolutionary pressure behind morphological adaptations of cell body location: In order to save energy, the electrical signal transmission from dendrite to axon can be enhanced if a relatively small cell body is located between dendrite and axon, while a relatively large cell body should be externalized. In the second project, it is shown that biophysical parameters, such as temperature, membrane leak or capacitance, can transform neuronal excitability (i.e., the spike onset bifurcation) and, with that, spike-based information processing. This thesis identifies the so-called saddle-node-loop bifurcation as the transition with particularly drastic functional implications. Besides altering neuronal filters and stimulus locking, the saddle-node-loop bifurcation leads to an increase in network synchronization, which may potentially be relevant for the initiation of seizures in response to increased temperature, such as during fever cramps.
|
| 23 |
TU-Spektrum 1/2007, Magazin der Technischen Universität ChemnitzSteinebach, Mario, Häckel-Riffler, Christine, Brabandt, Antje, Mahler, Janine, Chlebusch, Michael, Doriath, Thomas, Leidholdt, Nicole, Facius, Marlies 10 April 2007 (has links) (PDF)
zweimal im Jahr erscheinende Zeitschrift über aktuelle Themen der TU Chemnitz, ergänzt von Sonderheft(en)
|
| 24 |
TU-Spektrum 1/2007, Magazin der Technischen Universität ChemnitzSteinebach, Mario, Häckel-Riffler, Christine, Brabandt, Antje, Mahler, Janine, Chlebusch, Michael, Doriath, Thomas, Leidholdt, Nicole, Facius, Marlies 23 April 2007 (has links) (PDF)
zweimal im Jahr erscheinende Zeitschrift über aktuelle Themen der TU Chemnitz, ergänzt von Sonderheft(en)
neue Archivierung, da verbesserte Bildqualität
|
| 25 |
TU-Spektrum 1/2007, Magazin der Technischen Universität ChemnitzSteinebach, Mario, Häckel-Riffler, Christine, Brabandt, Antje, Mahler, Janine, Chlebusch, Michael, Doriath, Thomas, Leidholdt, Nicole, Facius, Marlies 10 April 2007 (has links)
zweimal im Jahr erscheinende Zeitschrift über aktuelle Themen der TU Chemnitz, ergänzt von Sonderheft(en)
|
| 26 |
TU-Spektrum 1/2007, Magazin der Technischen Universität ChemnitzSteinebach, Mario, Häckel-Riffler, Christine, Brabandt, Antje, Mahler, Janine, Chlebusch, Michael, Doriath, Thomas, Leidholdt, Nicole, Facius, Marlies 23 April 2007 (has links)
zweimal im Jahr erscheinende Zeitschrift über aktuelle Themen der TU Chemnitz, ergänzt von Sonderheft(en)
neue Archivierung, da verbesserte Bildqualität
|
Page generated in 0.0277 seconds