An Algorithm for Listing All Minimal 2-Dominating Sets of a Tree

Marcin Krzywkowski

An Algorithm for Listing All Minimal 2-Dominating Sets of a Tree

Abstract

We provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time O(1.3248n) . This implies that every tree has at most 1.3248 n minimal 2-dominating sets. We also show that this bound is tigh.

Author (1)

Marcin Krzywkowski dr inż.

Cite as

Full text

download paper

downloaded 16 times

Publication version: Accepted or Published Version
DOI:: Digital Object Identifier (open in new tab) 10.1007/978-3-642-38756-2_4
License: Copyright (2013 Springer-Verlag Berlin Heidelberg)

full content of the article see on external site open in new tab

Keywords

DOMINATION

Details

Category:: Articles
Type:: artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
Published in:: LECTURE NOTES IN COMPUTER SCIENCE no. 7924, pages 12 - 16,
ISSN: 0302-9743
Language:: English
Publication year:: 2013
Bibliographic description:: Krzywkowski M.: An Algorithm for Listing All Minimal 2-Dominating Sets of a Tree// LECTURE NOTES IN COMPUTER SCIENCE. -Vol. 7924., (2013), s.12-16
Verified by:: Gdańsk University of Technology