๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On-line algorithms for the dominating set problem

โœ Scribed by Gow-Hsing King; Wen-Guey Tzeng

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
346 KB
Volume
61
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

New On-Line Algorithms for the Page Repl
New On-Line Algorithms for the Page Replication Problem
โœ Susanne Albers; Hisashi Koga ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 210 KB

We present improved competitive on-line algorithms for the page replication problem and concentrate on important network topologies for which algorithms with a constant competitive ratio can be given. We develop an optimal randomized on-line replication algorithm for trees and uniform networks; its

Off-line algorithms for the list update
Off-line algorithms for the list update problem
โœ Nick Reingold; Jeffery Westbrook ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 637 KB

Optimum off-line algorithms for the list update problem are investigated. The list update problem involves implementing a dictionary of items as a linear list. Several characterizations of optimum algorithms are given; these lead to optimum algorithm which runs in time 02"( n -1) !m, where n is the

Distributed algorithms for finding the u
Distributed algorithms for finding the unique minimum distance dominating set in directed split-stars
โœ Fu-Hsing Wang; Jou-Ming Chang; Yue-Li Wang; Sun-Jen Huang ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 191 KB

A distance-k dominating set D of a directed graph G is a set of vertices such that for every vertex v of G; there is a vertex uAD and the distance between u and v is at most k: Minimum distance-k dominating set is especially important in communication networks for distributed data structures and for