Skip to main content
SpringerLink
Log in
Book cover

Exakte Algorithmen für schwere Graphenprobleme

  • Textbook
  • © 2010

Overview

Authors:
  1. Frank Gurski

    1. Inst. Informatik, Universität Düsseldorf, Düsseldorf, Germany

    View author publications

    You can also search for this author in PubMed   Google Scholar

  2. Irene Rothe

    1. , Fachbereich für Maschinenbau,, Hochschule Bonn-Rhein-Sieg, Sankt Augustin, Germany

    View author publications

    You can also search for this author in PubMed   Google Scholar

  3. Jörg Rothe

    1. Inst. Mathematik, Universität Düsseldorf, Düsseldorf, Germany

    View author publications

    You can also search for this author in PubMed   Google Scholar

  4. Egon Wanke

    1. , Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany

    View author publications

    You can also search for this author in PubMed   Google Scholar

  • Führt Studierende in besonders aktive Teilgebiete der Algorithmik ein Großer Wert wird auf Anschaulichkeit und Verständlichkeit der Darstellung gelegt Ausblicke, ausführliche Literaturhinweise, Übungsaufgaben und Probleme runden jedes Kapitel ab
  • Includes supplementary material: sn.pub/extras

Part of the book series: eXamen.press (EXAMEN)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 29.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 29.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (11 chapters)

  1. Front Matter

    Pages i-xii
    Download chapter PDF

  2. Einleitung

    • Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke
    Pages 1-4

  3. Grundlagen

    1. Front Matter

      Pages 5-5
      Download chapter PDF

    2. Aufwandsabschätzung von Algorithmen

      • Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke
      Pages 7-18

    3. Graphen

      • Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke
      Pages 19-64

    4. Logik

      • Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke
      Pages 65-103

    5. Komplexitätstheorie

      • Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke
      Pages 105-143

  4. Exakte Algorithmen für Graphen

    1. Front Matter

      Pages 145-145
      Download chapter PDF

  5. Exakte Algorithmen fur Graphen

    1. Fest-Parameter-Algorithmen für ausgewählte Graphenprobleme

      • Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke
      Pages 147-162

    2. Exponentialzeit-Algorithmen für Färbbarkeitsprobleme

      • Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke
      Pages 163-227

    3. Exponentialzeit-Algorithmen für TSP und DNP

      • Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke
      Pages 229-243

  6. Algorithmen auf speziellen Graphen

    1. Front Matter

      Pages 245-245
      Download chapter PDF

    2. Bäume und Co-Graphen

      • Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke
      Pages 247-258

    3. Baumweitebeschränkte Graphen

      • Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke
      Pages 259-284

    4. Cliquenweitebeschränkte Graphen

      • Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke
      Pages 285-306

  7. Back Matter

    Pages 307-331
    Download chapter PDF
Back to top

Keywords

About this book

Dieses Buch befasst sich mit schweren Problemen auf Graphen, für die es vermutlich keine effizienten Algorithmen gibt, und stellt verschiedene Methoden vor, wie man mit der algorithmischen Härte solcher Probleme umgehen kann. Einerseits kann man effiziente Algorithmen entwerfen, die sich eine geeignete Baumstruktur der Graphen zunutze machen; andererseits erlauben Fest-Parameter-Algorithmen eine effiziente Lösung, wenn gewisse Graphenparameter klein sind. Auch wenn diese Methoden nicht anwendbar sind, können die vorhandenen exakten Exponentialzeit-Algorithmen für solche schweren Probleme oft verbessert werden. Durch die leicht verständliche Darstellung, viele erklärende Abbildungen, Beispiele und Übungsaufgaben sowie die durchdachte Auswahl von Resultaten und Techniken ist dieses Buch besonders gut für den Einsatz in der Lehre geeignet, vor allem im Masterstudium Informatik und in den höheren Semestern des Bachelorstudiums Informatik. Gleichzeitig führt es den Leser unmittelbar an die Fronten der aktuellen Forschung in diesem neuen Teilgebiet der Algorithmik heran.

Authors and Affiliations

  • Inst. Informatik, Universität Düsseldorf, Düsseldorf, Germany

    Frank Gurski

  • , Fachbereich für Maschinenbau,, Hochschule Bonn-Rhein-Sieg, Sankt Augustin, Germany

    Irene Rothe

  • Inst. Mathematik, Universität Düsseldorf, Düsseldorf, Germany

    Jörg Rothe

  • , Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany

    Egon Wanke

About the authors

Prof. Dr. Jörg Rothe, lehrt an der Heinrich-Heine-Universität Düsseldorf, Institut für Informatik, Germany

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation