Author name cluster

David P. Jacobs

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

TCS Journal 2015 Journal Article

A theorem of Ore and self-stabilizing algorithms for disjoint minimal dominating sets

Stephen T. Hedetniemi
David P. Jacobs
K.E. Kennedy

A theorem of Ore [20] states that if D is a minimal dominating set in a graph G = ( V, E ) having no isolated nodes, then V − D is a dominating set. It follows that such graphs must have two disjoint minimal dominating sets R and B. We describe a self-stabilizing algorithm for finding such a pair of sets. It also follows from Ore's theorem that in a graph with no isolates, one can find disjoint sets R and B where R is maximal independent and B is minimal dominating. We describe a self-stabilizing algorithm for finding such a pair. Both algorithms are described using the Distance-2 model, but can be converted to the usual Distance-1 model [7], yielding running times of O ( n 2 m ).

Details DOI

TCS Journal 2008 Journal Article

Distance- k knowledge in self-stabilizing algorithms

Wayne Goddard
Stephen T. Hedetniemi
David P. Jacobs
Vilmar Trevisan

Many graph problems seem to require knowledge that extends beyond the immediate neighbors of a node. The usual self-stabilizing model only allows for nodes to make decisions based on the states of their immediate neighbors. We provide a general transformation for constructing self-stabilizing algorithms which utilize distance- k knowledge. Our transformation has both a slowdown and space overhead in n O ( log k ), and might be thought of as a distance- k resource allocation algorithm. Our main application is a polynomial-time self-stabilizing algorithm for finding maximal irredundant sets, a problem which seems to require distance-4 information. These results can be generalized to efficiently find maximal P -sets, for properties P which we call local monotonic. Our techniques extend results in a recent paper by Gairing et al. for achieving distance-two information.

Details DOI