Abstract
The focus of the present paper is on providing a local deterministic algorithm for colouring the edges of Yao-like subgraphs of Unit Disc Graphs. These are geometric graphs such that for some positive integers l,k the following property holds at each node v: if we partition the unit circle centered at v into 2k equally sized wedges then each wedge can contain at most l points different from v. We assume that the nodes are location aware, i.e. they know their Cartesian coordinates in the plane. The algorithm presented is local in the sense that each node can receive information emanating only from nodes which are at most a constant (depending on k and l, but not on the size of the graph) number of hops away from it, and hence the algorithm terminates in a constant number of steps. The number of colours used is 2kl + 1 and this is optimal for local algorithms (since the maximal degree is 2kl and a colouring with 2kl colours can only be constructed by a global algorithm), thus showing that in this class of graphs the price for locality is only one additional colour.
Keywords and Phrases: Edge Colouring, Geometric Graphs, Unit Disk Graphs, Local Algorithm, Location Awareness, Wedge, Wireless Network.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barrett, T.C., et al.: Strong edge coloring for channel assignment in wireless radio networks. In: IEEE International Workshop on Foundation and Algorithms for Wireless Networking, IEEE, New York (2006)
Kranakis, E., et al.: Half-Space Proximal: A New Local Test for Extracting a Bounded Dilation Spanner of a Unit Disk Graph. In: Anderson, J.H., Prencipe, G., Wattenhofer, R. (eds.) OPODIS 2005. LNCS, vol. 3974, pp. 235–245. Springer, Heidelberg (2006a)
Chavez, E., et al.: Local construction of planar spanners in unit disk graphs with irregular transmission ranges. In: Cardoso, J., Sheth, A.P. (eds.) SWSWPC 2004. LNCS, vol. 3387, pp. 286–297. Springer, Heidelberg (2005b)
Erdös, P.: On circuits and subgraphs of chromatic graphs. Mathematika 9, 170–175 (1962)
Gandham, S., Dawande, M., Prakash, R.: Link scheduling in sensor networks: distributed edge coloring revisited. In: INFOCOM, pp. 2492–2501. IEEE Computer Society Press, Los Alamitos (2005)
Holyer, I.: The NP-completeness of edge-coloring. SIAM Journal on Computing 10(4), 718–720 (1981)
Kodialam, M.S., Nandagopal, T.: Characterizing achievable rates in multi-hop wireless mesh networks with orthogonal channels. IEEE/ACM Trans. Netw. 13(4), 868–880 (2005)
Kumar, V.S.A., et al.: End-to-end packet-scheduling in wireless ad-hoc networks. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004, pp. 1021–1030. SIAM, Philadelphia (2004)
Li, X.-Y., et al.: Localized delaunay triangulation with application in ad hoc wireless networks. IEEE Trans. Parallel Distrib. Syst. 14(10), 1035–1047 (2003)
Linial, N.: Locality in distributed graph algorithms. SIAM Journal on Computing 21(1), 193–201 (1992)
Marathe, M.V., et al.: Simple heuristics for unit disk graphs. Networks 25(1), 59–68 (1995)
Matsui, T.: Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs. In: Akiyama, J., Kano, M., Urabe, M. (eds.) JCDCG 1998. LNCS, vol. 1763, pp. 194–200. Springer, Heidelberg (2000)
Naor, M., Stockmeyer, L.: What can be computed locally? SICOMP: SIAM Journal on Computing, vol. 24 (1995)
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)
Ramanathan, S.: A unified framework and algorithm for channel assignment in wireless networks. Wireless Networks 5(2), 81–94 (1999)
Vizing, V.G.: On the estimate of the chromatic class of a p-graph. Diskret. Analiz. 3, 25–30 (1964)
Wang, Y., Li, X.-Y.: Localized construction of bounded degree and planar spanner for wireless ad hoc networks. In: DialM: Proceedings of the Discrete Algorithms and Methods for Mobile Computing & Communications (2003)
Yao, A.: On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing 11(4), 721–736 (1982)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Czyzowicz, J., Dobrev, S., Kranakis, E., Opatrny, J., Urrutia, J. (2007). Local Edge Colouring of Yao-Like Subgraphs of Unit Disk Graphs. In: Prencipe, G., Zaks, S. (eds) Structural Information and Communication Complexity. SIROCCO 2007. Lecture Notes in Computer Science, vol 4474. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72951-8_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-72951-8_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72918-1
Online ISBN: 978-3-540-72951-8
eBook Packages: Computer ScienceComputer Science (R0)