TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. browse.metadata.tuhhjournals.breadcrumbs

Browsing by browse.metadata.tuhhjournals "Algorithm Engineering Report"

Now showing1 - 1 of 1
Results Per Page
Sort Options
  • Some of the metrics are blocked by your 
    consent settings
    Publicationwithout files
    Effiziente Extraktion von Kuratowski-Teilgraphen
    (Techn. Univ. Dortmund, 2007-03-16)
    Schmidt, Jens M.  orcid-logo
    Ein Graph ist nach dem Satz von Kuratowski genau dann planar, wenn er keine Kuratowski-Subdivisions enth\"alt. Eine einzelne davon kann von modernen Planarit\"atstests bei nicht planaren Eingabegraphen in Linearzeit extrahiert werden. Allerdings existieren Anwendungen, die nicht nur eine, sondern m\"oglichst viele dieser Kuratowski-Subdivisions ben\"otigen. Dazu geh\"oren Branch-and-Cut-Algorithmen f\"ur einige NP-schwere Probleme, wie beispielsweise die Kreuzungsminimierung oder auch verschiedene Varianten des Maximum Planar Subgraph Problems. Die Kuratowski-Subdivisions erm\"oglichen dort die Berechnung von zus\"atzlichen nebenbedingungen einer LP-Relaxierung. Dabei ist es w\"unschenswert, dass die Kuratowski-Subdivisions paarweise entweder m\"oglichst viele Kanten gemeinsam haben oder weitgehend kantendisjunkt sind. In dieser Diplomarbeit wird ein Algorithmus entworfen und analysiert, der mehrere Kuratowski-Subdivisions in linearer Zeit O(n + m + Sum_(K in S) |E(K)|) extrahieren kann, wobei S die Menge der gefundenen Kuratowski-Subdivisions ist. Dieser Algorithmus stellt eine Erweiterung des aktuellen Planarit\"atstests von Boyer und Myrvold dar und kann zus\"atzlich so modifiziert werden, dass entweder m\"oglichst \"ahnliche oder m\"oglichst verschiedene Kuratowski-Subdivisions ausgegeben werden. Die Laufzeit des Algorithmus ist dabei asymptotisch optimal. Aus diesem Algorithmus wird ein zweiter Ansatz entwickelt, der in der Praxis mehr Kuratowski-Subdivisions extrahieren kann, daf\"ur aber zu einer superlinearen Laufzeit f\"uhrt. Beide Verfahren werden implementiert und deren Praxistauglichkeit verglichen.
    Publicationtype: Master Thesis
    Thesistype: masterThesis
    Citation Publisher Version:Masterarbeit, Fachbereich Informatik der Universität Dortmund: 2007,4 (2007)
      66
TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback