![]() SIAM J Comput 33(1):94–136įiala J, Fishkin AV, Fomin F (2004) On distance constrained labeling of disk graphs. Society for Industrial and Applied Mathematics, Philadelphia, pp 671–679Įven G, Lotker Z, Ron D, Smorodinsky S (2004) Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. In: SODA '01: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. Springer, pp 135–155Įrlebach T, Jansen K, Seidel E (2001) Polynomial-time approximation schemes for geometric graphs. In: Bampis E, Jansen K, Kenyon C (eds) Efficient Approximation and Online Algorithms, vol 3484 of Lecture Notes in Computer Science. J Global Optim 28(1):115–119Įrlebach T, Fiala J (2006) Independence and coloring problems on intersection graphs of disks. Theoret Comput Sci 377(1–3):271–276ĭu H, Jia X, Li D, Wu W (2004) Coloring of double disk graphs. In: Proceedings of the International Conference on Computers and Communication Networks (IC3N), pp 1–20ĭiaz J, Kaminski M (2007) Max-cut and max-bisection are np-hard on unit disk graphs. In: Proceedings of IEEE International Conference on Communications, pp 376–380ĭas B, Sivakumar R, Bharghavan V (1997) Routing in ad-hoc networks using a virtual backbone. Discret Math 86:165–177ĭas B, Bharghavan V (1997) Routing in ad-hoc networks using minimum connected dominating sets. Netw 42(4):202–208Ĭlark BN, Colbourn CJ, Johnson DS (1990) Unit disk graphs. ![]() ![]() J Cluster Computing, Special Issue on Mobile Ad hoc Netw 5:193–204Ĭheng X, Huang X, Li D, Wu W, Du DZ (2003) A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Elsevier, Amsterdam, pp 73–79 (electronic)Ĭhatterjee M, Das S, Turgut D (2002) WCA: A weighted clustering algorithm for mobile ad hoc networks. In: Latin-American Conference on Combinatorics, Graphs and Applications, vol 18 of Electronic Notes in Discrete Mathematics. In: Caulfield HJ, Chen SH, Cheng HD, Duro RJ, Honavar V, Kerre EE, Lu M, Romay MG, Shih TK, Wang DVPP, Yang Y (eds) Proceedings of the 6th Joint Conference on Information Science JCIS/Association for Intelligent Machinery, Inc, pp 251–255Ĭerioli MR, Faria L, Ferreira TO, Protti F (2004) On minimum clique partition and maximum independent set on unit disk graphs and penny graphs: complexity and approximation. Society for Industrial and Applied Mathematics, Philadelphia, pp 263–272Ĭardei M, Cheng X, Cheng X, Du DZ (2002) Connected domination in multihop ad hoc wireless networks. In: Proceedings of the sixth annual ACM-SIAM symposium on discrete algorithms (SODA '95). Kluwer Academic, pp 43–54Ĭallahan PB, Kosaraju SR (1995) Algorithms for dynamic closest pair and n-body potential fields. In Butenko S, Murphey R, Pardalos PM (eds), Cooperative Control: Models, Applications and Algorithms. Proc Cambridge Philos Soc 37:194–197īutenko S, Cheng X, Du DZ, Pardalos P (2003) On the construction of virtual backbone for ad hoc wireless networks. Comput Geometr Theory Applīrooks RL (1941) On coloring the nodes of a network. University of British Columbiaīreu H, Kirkpatrick DG (1998) Unit disk graph recognition is NP-hard. In Proceedings of the (1999) International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99) p 310īreu H (1996) Algorithmic Aspects of Constrained Unit Disk Graphs, PhD thesis. Ann Discret Math 25:27–46īasagni S (1999) Distributed clustering for ad hoc networks. In: STOC '82: Proceeding of the Fourteenth Annual ACM Symposium on Theory of Computing, pp 303–309īar-Yehuda R, Even S (1985) A local-ratio theorem for approximating the weighted vertex cover problem. Spinger, New York, pp 865–890īar-Yehuda R, Even S (1982) On approximating a vertex cover for planar graphs. In: Resende MGC, Pardalos PM (eds) Handbook of Optimization in Telecommunications. J ACM 41(1):153–180īalasundaram B, Butenko S (2006) Graph domination, coloring and cliques in telecommunications. pp 3–14īaker BS (1994) Approximation algorithms for NP‑complete problems on planar graphs. In: Diaz J, Jansen K, Rolim JDP, Zwick U (eds) Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques vol 4110 of Lecture Notes in Computer Science. J Commun Netw 4:22–29Īmbühl C, Erlebach T, Mihal'ák M, Nunkesser M (2006) Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs. J Algorithm 52(2):134–151Īlzoubi KM, Wan PJ, Frieder O (2002) Distributed heuristics for connected dominating sets in wireless ad hoc networks. Alber J, Fiala J (2004) Geometric separation and exact solutions for the parameterized independent set problem on disk graphs.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |