zum Inhalt

 

Nguyen,  Ngoc Tuy

Graph Powers: Hardness Results, Good Characterizations and Efficient Algorithms

Rostock : Universität , 2009

https://doi.org/10.18453/rosdok_id00000580

http://purl.uni-rostock.de/rosdok/id00000580

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.

Dissertation Open Access


Einrichtung :
Fakultät für Informatik und Elektrotechnik
Gutachter :
Le,  Van Bang  (Prof. Dr.)
Wanke,  Egon  (Prof. Dr.)
Köhler,  Ekkehard  (Prof. Dr.)
Jahr der Abgabe:
2009
Jahr der Verteidigung:
2009
Sprache(n) :
Englisch
Schlagworte:
computational complexity, graph algorithms, graph classes
DDC Klassifikation :
004 Informatik
URN :
urn:nbn:de:gbv:28-diss2009-0206-0
Persistente URL:
http://purl.uni-rostock.de/rosdok/id00000580
erstellt am:
2010-01-15
zuletzt geändert am:
2018-06-30
Volltext