EuDML | Browse

Skip to main content (access key 's'), Skip to navigation (access key 'n'), Accessibility information (access key '0')

Subjects
68-XX Computer science
68Wxx Algorithms
68W05 Nonnumerical algorithms

Items

All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1

Displaying 1 – 1 of 1

Minimal 2-dominating sets in trees

Marcin Krzywkowski (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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

Currently displaying 1 – 1 of 1

Page 1