nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Approximate Strong Edge-Colouring of Unit Disk Graphs

verfasst von : Nicolas Grelier, Rémi de Joannis de Verclos, Ross J. Kang, François Pirot

Erschienen in: Approximation and Online Algorithms

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We show that the strong chromatic index of unit disk graphs is efficiently 6-approximable. This improves on 8-approximability as shown by Barrett, Istrate, Kumar, Marathe, Thite, and Thulasidasan [1]. We also show that strong edge-6-colourability is NP-complete for the class of unit disk graphs. Thus there is no polynomial-time \((7/6-\varepsilon )\)-approximation unless P = NP.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel On the Cycle Augmentation Problem: Hardness and Approximation Algorithms

Nächstes Kapitel Precedence-Constrained Scheduling and Min-Sum Set Cover

To avoid any ambiguity, in the online setting vertices are revealed one at a time and all edges between a newly revealed vertex and previous vertices must be immediately and irrevocably assigned a colour.

Barrett, C.L., Istrate, G., Anil Kumar, V.S., Marathe, M.V., Thite, S., Thulasidasan, S.: Strong edge coloring for channel assignment in wireless radio networks. In: 2006 Pervasive Computing and Communications Workshops, p. 5. IEEE (2006)

Bonamy, M., Perrett, T., Postle, L.: Colouring graphs with sparse neighbourhoods: bounds and applications. arXiv e-prints:1810.06704 (2018)

Bruhn, H., Joos, F.: A stronger bound for the strong chromatic index. Combin. Probab. Comput. 27(1), 21–43 (2018). https://doi.org/10.1017/S0963548317000244MathSciNetCrossRefMATH

Chalermsook, P., Laekhanukit, B., Nanongkai, D.: Coloring graph powers: graph product bounds and hardness of approximation. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 409–420. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54423-1_36CrossRef

Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Math. 86(1–3), 165–177 (1990)MathSciNetCrossRef

Diestel, R.: Graph theory, Graduate Texts in Mathematics, 5th edn, vol. 173. Springer, Berlin (2017). https://doi.org/10.1007/978-3-662-53622-3CrossRef

Erdős, P.: Problems and results in combinatorial analysis and graph theory. In: Proceedings of the First Japan Conference on Graph Theory and Applications, Hakone, 1986, vol. 72, pp. 81–92 (1988). https://doi.org/10.1016/0012-365X(88)90196-3MathSciNetCrossRef

Gräf, A., Stumpf, M., Weißenfels, G.: On coloring unit disk graphs. Algorithmica 20(3), 277–293 (1998)MathSciNetCrossRef

Hale, W.K.: Frequency assignment: theory and applications. Proc. IEEE 68(12), 1497–1514 (1980). https://doi.org/10.1109/PROC.1980.11899CrossRef

10.

Kaiser, T., Kang, R.J.: The distance-\(t\) chromatic index of graphs. Combin. Probab. Comput. 23(1), 90–101 (2014). https://doi.org/10.1017/S0963548313000473MathSciNetCrossRefMATH

11.

Kang, R.J., Müller, T.: Sphere and dot product representations of graphs. Discrete Comput. Geom. 47(3), 548–568 (2012). https://doi.org/10.1007/s00454-012-9394-8MathSciNetCrossRefMATH

12.

Kanj, I.A., Wiese, A., Zhang, F.: Local algorithms for edge colorings in UDGs. Theor. Comput. Sci. 412(35), 4704–4714 (2011). https://doi.org/10.1016/j.tcs.2011.05.005MathSciNetCrossRef

13.

Mahdian, M.: The strong chromatic index of graphs. Master’s thesis, University of Toronto (2000)

14.

Mahdian, M.: On the computational complexity of strong edge coloring. Discrete Appl. Math. 118(3), 239–248 (2002). https://doi.org/10.1016/S0166-218X(01)00237-2MathSciNetCrossRefMATH

15.

Malesińska, E., Piskorz, S., Weißenfels, G.: On the chromatic number of disk graphs. Networks 32(1), 13–22 (1998)MathSciNetCrossRef

16.

Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Simple heuristics for unit disk graphs. Networks 25(2), 59–68 (1995)MathSciNetCrossRef

17.

Molloy, M., Reed, B.: A bound on the strong chromatic index of a graph. J. Combin. Theory Ser. B 69(2), 103–109 (1997). https://doi.org/10.1006/jctb.1997.1724MathSciNetCrossRefMATH

18.

Nandagopal, T., Kim, T.E., Gao, X., Bharghavan, V.: Achieving MAC layer fairness in wireless packet networks. In: Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, pp. 87–98. ACM (2000)

19.

Peeters, R.: On coloring j-unit sphere graphs. Technical report, Tilburg University (1991)

20.

Ramanathan, S., Lloyd, E.L.: Scheduling algorithms for multihop radio networks. IEEE/ACM Trans. Netw. (TON) 1(2), 166–177 (1993)CrossRef

21.

de Joannis de Verclos, R., Kang, R.J., Pastor, L.: Colouring squares of claw-free graphs. Can. J. Math. 71(1), 113–129 (2019). https://doi.org/10.4153/CJM-2017-029-9MathSciNetCrossRef

Titel: Approximate Strong Edge-Colouring of Unit Disk Graphs
verfasst von: Nicolas Grelier
Rémi de Joannis de Verclos
Ross J. Kang
François Pirot
Verlag: Springer International Publishing
Buch: Approximation and Online Algorithms
Print ISBN: 978-3-030-39478-3

Electronic ISBN: 978-3-030-39479-0

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-39479-0_11

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"