Maak een nieuw boekenlijstje

Dit kun je altijd nog aanpassen

Annuleer

Be sparse! Be dense! Be robust!

Elements of parameterized algorithmics

In dieser Dissertation untersuchen wir die Berechnungskomplexität von fünf NP-schweren Graphproblemen. Es wird weithin angenommen, dass NP-schwere Probleme im Allgemeinen nicht effizient gelöst werden können, das heißt, dass sie keine Polynomialzeitalgorithmen erlauben. Diese Annahme basiert auf vielen bisher nicht erfolgreichen Versuchen das Gegenteil zu beweisen. Aus diesem Grund versuchen wir Eigenschaften der Eingabe herauszuarbeiten, die das betrachtete Problem handhabbar oder unhandhabbar machen. Solche Eigenschaften messen wir mittels Parametern, das heißt, Abbildungen, die jeder möglichen Eingabe eine natürliche Zahl zuordnen. Für einen gegebenen Parameter k versuchen wir dann Fixed-Parameter Algorithmen zu entwerfen, also Algorithmen, die auf Eingabe q eine obere Laufzeitschranke von f(k(q)) * |q|^c erlauben, wobei f eine, vorzugsweise schwach wachsende, Funktion ist, |q| die Länge der Eingabe, und c eine Konstante, vorzugsweise klein. In den Graphproblemen, die wir in dieser Dissertation studieren, repräsentiert unsere Eingabe eine Situation in der wir einen Lösungsgraph finden sollen. Zusätzlich sollen die Lösungsgraphen bestimmte problemspezifische Eigenschaften haben. Wir betrachten drei Varianten dieser Eigenschaften: Zunächst suchen wir einen Graphen, der sparse sein soll. Das heißt, dass er wenige Kanten enthalten soll. Dann suchen wir einen Graphen, der dense sein soll. Das heißt, dass er viele Kanten enthalten soll. Zuletzt suchen wir einen Graphen, der robust sein soll. Das heißt, dass er eine gute Lösung bleiben soll, selbst wenn er einige kleine Modifikationen durchmacht. Be sparse! In diesem Teil der Arbeit analysieren wir zwei ähnliche Probleme. In beiden ist die Eingabe ein Hypergraph H, bestehend aus einer Knotenmenge V und einer Familie E von Teilmengen von V, genannt Hyperkanten. Die Aufgabe ist einen Support für H zu finden, einen Graphen G, sodass für jede Hyperkante W in E der induzierte Teilgraph G(W) verbunden ist. Motiviert durch Anwendungen im Netzwerkdesign betrachten wir SUBSET INTERCONNECTION DESIGN, worin wir eine natürliche Zahl f als zusätzliche Eingabe bekommen, und der Support höchstens |V| - f + 1 Kanten enthalten soll. Wir zeigen, dass SUBSET INTERCONNECTION DESIGN einen Fixed-Parameter Algorithmus in Hinsicht auf die Zahl der Hyperkanten im Eingabegraph erlaubt, und einen Fixed-Parameter Algorithmus in Hinsicht auf f + d, wobei d die Größe einer größten Hyperkante ist. Motiviert durch eine Anwendung in der Hypergraphvisualisierung studieren wir r-OUTERPLANAR SUPPORT, worin der Support für H r-outerplanar sein soll, das heißt, er soll eine kantenkreuzungsfreie Einbettung in die Ebene erlauben mit höchstens r Schichten. Wir zeigen, dass r-OUTERPLANAR SUPPORT einen Fixed-Parameter Algorithmus in Hinsicht auf m + r zulässt, wobei m die Anzahl der Hyperkanten im Eingabehypergraphen H ist. Be dense! In diesem Teil der Arbeit studieren wir zwei Probleme, die durch Community Detection in sozialen Netzwerken motiviert sind. Dabei ist die Eingabe ein Graph G und eine natürliche Zahl k. Wir suchen einen Teilgraphen G' von G, der (genau) k Knoten enthält und dabei eine von zwei mathematisch präzisen Definitionen davon, dense zu sein, aufweist. In mu-CLIQUE, 0 < mu <= 1, soll der gesuchte Teilgraph G' mindestens mu mal k über 2 Kanten enthalten. Wir studieren die Berechnungskomplexität von mu-CLIQUE in Hinsicht auf drei Parameter des Eingabegraphen G: dem maximalen Knotengrad delta, dem h-Index h, und der Degeneracy d. Es gilt delta >= h >= d für jeden Graphen und h als auch d nehmen kleine Werte in Graphen an, d
Zet op boekenlijstje
 
We geven korting vanaf je 4e boek in 12 maanden. Zonder gedoe.  Lees meer.
17,99
 14,99
 
We geven korting vanaf je 4e boek in 12 maanden. Zonder gedoe.  Lees meer.
17,99
 14,99

1 - 2 Weken

Beoordeling lezers

  • 0 sterren

Wat vond jij van dit boek?

Hoeveel sterren geef je?

Geef je uitgebreide beoordeling en maak kans op een fantastisch boekenpakket met 3 titels uit de Bestseller top 100.

  1. Geef je mening in je eigen woorden, dat is veel leuker om te lezen.
  2. Prijzen kun je beter niet noemen. Die veranderen nog wel eens.
  3. Noem geen persoonlijke informatie over jezelf of anderen, je beoordeling is door iedereen te zien.
  4. Links naar andere leestips? Ja graag! Informatie over andere bedrijven of websites, nee dankje.
  5. Tot slot: blijf netjes, want ongepaste taal kunnen we natuurlijk niet plaatsen.
 

Voorbeeld beoordeling:

Nog even geduld, je beoordeling komt meestal binnen een dag online!

  • Auteur(s) : Manuel Sorge
  • Uitgeverij : Universitätsverlag Tu Ber
  • ISBN : 9783798328853
  • Taal : Engels
  • Uitvoering : Hardcover (ENG)
  • Verschijningsdatum : 01-01-2017
  • Afmetingen : 212 x 149 x 22 mm.
  • Gewicht : 508 gr.