Tree Projections: Game Characterization and Computational Aspects

The notion of tree projection provides a natural generalization for various structural decomposition methods, which have been proposed in the literature in order to single out classes of nearly-acyclic (hyper)graphs. In this paper, the mathematical properties of the notion of tree projection are overviewed, and the complexity of the basic tree projection problem (of deciding the existence of a tree projection) is depicted. In more details, a game-theoretic characterization (in terms of the Robber and Captain game [15]) for tree projections is described, which also serves to provide simple arguments for the membership in NP of the tree projection problem. Eventually, the main ideas proposed in [14] and underlying the proof of NP-hardness of the tree projection problem are discussed.


Editor(s):
Lipshteyn, Marina
Levit, Vadim E.
McConnell, Ross M.
Published in:
Graph Theory, Computational Intelligence and Thought. Essays Dedicated to Martin Charles Golumbic on the Occasion of His 60th Birthday, 87--99
Year:
2009
Publisher:
Springer
Laboratories:




 Record created 2009-09-21, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)