Publikation: Dissertationsschrift

Graph powers

Grunddaten
Abstract
Autoren
Einrichtung

Grunddaten

Titel	Graph powers
Untertitel	hardness results, good characterizations and efficient algorithms
Erscheinungsjahr	2009
Publikationsform	Elektronische Ressource
Publikationsart	Dissertationsschrift
Sprache	Englisch
Letzte Änderung	19.03.2013 10:51:15
Bearbeitungsstatus	durch UB Rostock abschließend validiert
Dauerhafte URL	http://purl.uni-rostock.de/fodb/pub/32142
Links zu Katalogen

Abstract

Given a graph H = (V_H,E_H) and a positive integer k, the k-th power of H, written H^k, is the graph obtained from H by adding edges between any pair of vertices at distance at most k in H; formally, H^k = (V_H, {xy | 1 <= d_H (x, y) <= k}). A graph G is the k-th power of a graph H if G = H^k, and in this case, H is a k-th root of G. Our investigations deal with the computational complexity of recognizing k-th powers of general graphs as well as restricted graphs. This work provides new NP-completeness results, good characterizations and efficient algorithms for graph powers.

Autor

Nguyen, Ngoc Tuy

Einrichtung

IEF/Bereich Informatik