zum Inhalt


Ngoc Tuy Nguyen

Graph Powers: Hardness Results, Good Characterizations and Efficient Algorithms

Universität Rostock, 2009

https://doi.org/10.18453/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   Freier Zugang    


Portale

OPACGVKDataCite Commons

Rechte

alle Rechte vorbehalten

Das Werk darf ausschließlich nach den vom deutschen Urheberrechtsgesetz festgelegten Bedingungen genutzt werden.