de
en
Schliessen
Detailsuche
Bibliotheken
Projekt
Impressum
Datenschutz
Schliessen
Publizieren
Besondere Sammlungen
Digitalisierungsservice
Hilfe
Impressum
Datenschutz
zum Inhalt
Detailsuche
Schnellsuche:
OK
Ergebnisliste
Titel
Titel
Inhalt
Inhalt
Seite
Seite
Im Werk suchen
Tscheuschner, Tobias: The complexity of local max-cut. 2012
Inhalt
Introduction
Local search
Contribution of This Thesis
Further Related Work
Preliminaries
Basic Notations
Local Search
Local Max-Cut
Boolean Circuits and Boolean Formulas
Complexity of Local Max-Cut: Maximum Degree Four
Overview of Contribution
Basic Properties of Nodes with Maximum Degree Four
P-hardness for Graphs with Nodes of Type I and III
Is-Exp Property for Graphs with Nodes of Type I and III
Enforcing Technique for Graphs with Nodes of Type I, II and III
Basic Subgraphs
Combining the Subgraphs
Enforcing Pivot-Rules with Combined Subgraphs
All-Exp Property
PSPACE-completeness of the Standard Algorithm Problem
Complexity of Local Max-Cut: Maximum Degree Five
Overview of Contribution
Usage of the P-hardness Reduction
Substituting Certain Nodes of Unbounded Degree
PLS-completeness
Impact of the Results on Other Problems
Max-2SAT with FLIP-neighborhood
Congestion Games
Partitioning with SWAP-neighborhood
Conclusion and Open Problems
Bibliography
Die detaillierte Suchanfrage erfordert aktiviertes Javascript.