The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 28 NO.4 / (1999))
Local Labeling and Resource Allocation Using Preprocessing
Hagit Attiya, Hadas Shachnai, Tami Tamir,
Pages. 1397-1413
Abstract
Contents 1. Introduction
2. Preliminaries
3. Labeling problems
3.1. A lower bound
3.2. Efficient labeling using $t$-orientation
4. Resource allocation
4.1. A lower bound for $k$-compact resource allocation
4.2. Compact coloring
4.3. A distributed $mu$-compact resource allocation algorithm
4.4. Discussion
5. Conclusions and open problems
Key words locality, preprocessing, orientation, labeling, resource allocation, response time
Mathmatical Subject Classification 68P05, 68Q10, 68Q20, 68Q22, 68