Some Domination Problems on Trees and on General Graphs

摘要

Several variants of domination problems are studied. Linear time algorithms aregiven for path domination, independent efficient domination, and efficient total domination on trees. On the other hand, it is proven that these problems are NP complete for general graphs. All domination problems studied are derived from considerations about distributed data structuring and resource allocation in communication networks.