Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Onk-Strong Conflict–Free Multicoloring

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 10628))

Abstract

Let\(\mathcal{H}=(\mathcal{V},\mathcal{E})\) be a hypergraph. Ak-strong conflict-free coloring of\(\mathcal{H}\) is an assignment of colors to the members of the vertex set\(\mathcal{V}\) such that every hyperedge\(E\in \mathcal{E}\),\(|E|\ge k\), containsk nodes whose colors are pairwise distinct and different from the colors assigned to all the other nodes inE, whereas if\(|E|<k\) all nodes inE get distinct colors. The parameter to optimize is the total number of colors. The need for such colorings originally arose as a problem of frequency assignment for cellular networks, but since then it has found applications in a variety of different areas. In this paper we consider a generalization of the above problem, where one is allowed to assignmore than one color to each node. When\(k=1\), our generalization reduces to theconflict-free multicoloring problem introduced by Even et al. [2003], and recently studied by Bärtschi and Grandoni [2015], and Ghaffari et al. [2017]. We motivate our generalized formulation and we point out that it includes a vast class of well known combinatorial and algorithmic problems, when the hypergraph\(\mathcal{H}\) and the parameterk are properly instantiated. Our main result is an algorithm to construct ak-strong conflict-free multicolorings of an input hypergraph\(\mathcal{H}\) that utilizes a total number of colors\(O( \min \{(k+\log ({r}/{k}) )\log {\varGamma }+ k( k+\log ^2 ({r}/{k})), \ (k^2 + r ) \log n \})\), wheren is the number of nodes,\(r\) is the maximum hyperedge size, and\({\varGamma }\) is the maximum hyperedge degree; the expected number of colors per node is\(O(\min \{k+\log {\varGamma }, \ (k + \log ({r}/{k})) \log n \})\). Although derived for arbitraryk, our result improves on the corresponding result by Bärtschi and Grandoni [2015], when instantiated for\(k=1\). We also provide lower bounds on the number of colors neededin anyk-strong conflict-free multicoloring, thus showing that our algorithm is not too far from being optimal.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Similar content being viewed by others

Notes

  1. 1.

    The Hamming weight of a vector/row is the number of symbols that are different from 0 in the vector/row.

  2. 2.

    Essentially, the algorithm works as follows: After a first random evaluation ofP, it keeps resampling violated events\(A\in \mathcal{A}\) until none remains.

References

  1. Abam, M.A., de Berg, M., Poon, S.H.: Fault-tolerant conflict-free coloring. In: Proceedings of 20th Canadian Conference on Computational Geometry (CCCG) (2008)

    Google Scholar 

  2. Abellanas, M., Bose, P., García, J., Hurtado, F., Nicolás, C.M., Ramos, P.: On structural and graph theoretic properties of higher order delaunay graphs. Int. J. Comput. Geom. Appl.19, 595 (2009)

    Article MATH MathSciNet  Google Scholar 

  3. Alon, N., Fachini, E., Korner, J.: Locally thin set families. Comb. Probab. Comput.9, 481–488 (2000)

    Article MATH MathSciNet  Google Scholar 

  4. Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley-Interscience Series in Discrete Mathematics and Optimization, 3rd edn. John Wiley & Sons Inc., Hoboken (2008)

    Book MATH  Google Scholar 

  5. Bärtschi, A., Grandoni, F.: On conflict-free multi-coloring. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 103–114. Springer, Cham (2015).https://doi.org/10.1007/978-3-319-21840-3_9

    Chapter  Google Scholar 

  6. de Berg, M., Leijsen, T., van Renssen, A., Roeloffzen, M., Markovic, A., Woeginger, G.: Dynamic and kinetic conflict-free coloring of intervals with respect to points, arXiv preprintarXiv:1701.03388 (2017)

  7. Blundo, C., Galdi, C., Persiano, P.: Randomness recycling in constant-round private computations. In: Jayanti, P. (ed.) DISC 1999. LNCS, vol. 1693, pp. 140–149. Springer, Heidelberg (1999).https://doi.org/10.1007/3-540-48169-9_10

    Chapter  Google Scholar 

  8. Chaudhuri, S., Radhakrishnan, J.: Deterministic restrictions in circuit complexity. In: Proceedings of 28th STOC, pp. 30–36 (1996)

    Google Scholar 

  9. Cheilaris, P., Gargano, L., Rescigno, A.A., Smorodinsky, S.: Strong conflict-free coloring for intervals. Algorithmica70(4), 732–749 (2014)

    Article MATH MathSciNet  Google Scholar 

  10. Chlebus, B.S., Kowalski, D.R.: Almost optimal explicit selectors. In: Liśkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol. 3623, pp. 270–280. Springer, Heidelberg (2005).https://doi.org/10.1007/11537311_24

    Chapter  Google Scholar 

  11. Clementi, A.E.F., Monti, A., Silvestri, R.: Distributed broadcast in radio networks of unknown topology. Theor. Comput. Sci.302(1–3), 337–364 (2003)

    Article MATH MathSciNet  Google Scholar 

  12. Cormode, G., Muthukrishnan, S.: Combinatorial algorithms for compressed sensing. In: Flocchini, P., Gąsieniec, L. (eds.) SIROCCO 2006. LNCS, vol. 4056, pp. 280–294. Springer, Heidelberg (2006).https://doi.org/10.1007/11780823_22

    Chapter  Google Scholar 

  13. De Bonis, A., Gasieniec, L., Vaccaro, U.: Optimal two-stage algorithms for group testing problems. SIAM J. Comput.34(5), 1253–1270 (2005)

    Article MATH MathSciNet  Google Scholar 

  14. Du, D.Z., Hwang, F.K.: Combinatorial Group Testing and its Applications. World Scientific, River Edge (2000)

    MATH  Google Scholar 

  15. Du, D.Z., Hwang, F.K.: Pooling Designs and Nonadaptive Group Testing. World Scientific, Singapore (2006)

    Book MATH  Google Scholar 

  16. Dua, A.: Random access with multi-packet reception. IEEE Trans. Wirel. Commun.7(6), 2280–2288 (2008)

    Article  Google Scholar 

  17. D’yachkov, A.G., Rykov, V.V.: Bounds on the length of disjunct codes. Problemy Peredachi Informatsii18(3), 7–13 (1982)

    Google Scholar 

  18. D’yachkov, A.G., Vorobév, I.V., Polyansky, N.A., Shchukin, V.Y.: Bounds on the rate of disjunctive codes. Prob. Inform. Transm.50(1), 27–56 (2014)

    Google Scholar 

  19. D’yachkov, A.G., Vorobév, I.V., Polyansky, N.A., Shchukin, V.Y.: Erratum to: bounds on the rate of disjunctive codes. Prob. Inform. Transm.52(2), 200 (2016). Problems of Information Transmission 50, 27 (2014)

    Google Scholar 

  20. Erdös, P., Frankl, P., Füredi, Z.: Families of finite sets in which no set is covered by the union of\(r\) others. Israel J. Math.51, 75–89 (1985)

    Article MATH MathSciNet  Google Scholar 

  21. Even, G., Lotker, Z., Ron, D., Smorodinsky, S.: Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM J. Comput.33, 94–136 (2003)

    Article MATH MathSciNet  Google Scholar 

  22. Gargano, L., Rescigno, A.A.: Complexity of conflict-free colorings of graphs. Theor. Comput. Sci.566, 39–49 (2015)

    Article MATH MathSciNet  Google Scholar 

  23. Ghaffari, M., Kuhn, F., Maus, Y.: On the complexity of local distributed graph problems. In: Proceedings of ACM Symposium on Theory of Computing (STOC) (2017, to appear)

    Google Scholar 

  24. Glebov, R., Szabó, T., Tardos, G.: Conflict-free coloring of graphs. Comb. Prob. Comput.23(3), 434–448 (2014)

    Article MATH  Google Scholar 

  25. Horev, E., Krakovski, R., Smorodinsky, S.: Conflict-free coloring made stronger. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol. 6139, pp. 105–117. Springer, Heidelberg (2010).https://doi.org/10.1007/978-3-642-13731-0_11

    Chapter  Google Scholar 

  26. Katz, M., Lev-Tov, N., Morgenstern, G.: Conflict-free coloring of points on a line with respect to a set of intervals. Comp. Geom.45(9), 508–514 (2012)

    Article MATH MathSciNet  Google Scholar 

  27. Kautz, W.H., Singleton, R.C.: Nonrandom binary superimposed codes. IEEE Trans. Inf. Theor.10, 363–377 (1964)

    Article MATH  Google Scholar 

  28. Kumar, R., Rajagopalan, S., Sahai, A.: Coding constructions for blacklisting problems without computational assumptions. In: Proceedings of CRYPTO 1999, pp. 609–623 (1999)

    Google Scholar 

  29. Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput.21, 193–201 (1992)

    Article MATH MathSciNet  Google Scholar 

  30. Moser, R.A., Tardos, G.: A constructive proof of the general Lovász local lemma. J. ACM57(2), 1–15 (2010)

    Article MATH  Google Scholar 

  31. Pach, J., Tardos, G.: Conflict-free colorings of graphs and hypergraphs. Comb. Prob. Comput.18(5), 819–834 (2009)

    Article MATH  Google Scholar 

  32. Porat, B., Porat, E.: Exact and approximate pattern matching in the streaming model. In: Proceedings of 50th FOCS, pp. 315–323 (2009)

    Google Scholar 

  33. Ruszinkó, M.: On the upper bound of the size of the\(r\)-cover-free families. J. Comb. Theor. Ser. A66, 302–310 (1994)

    Article MATH MathSciNet  Google Scholar 

  34. Smorodinsky, S.: Conflict-Free Coloring and its Applications, Geometry – Intuitive, Discrete, and Convex: A Tribute to László Fejes Tóth, pp. 331–389. Springer, Heidelberg (2013). Bárány, I., Böröczky, K.J., Tóth, G.F., Pach, J. (eds.)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Informatica, University of Salerno, 84084, Fisciano, SA, Italy

    Luisa Gargano, Adele A. Rescigno & Ugo Vaccaro

Authors
  1. Luisa Gargano

    You can also search for this author inPubMed Google Scholar

  2. Adele A. Rescigno

    You can also search for this author inPubMed Google Scholar

  3. Ugo Vaccaro

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toUgo Vaccaro.

Editor information

Editors and Affiliations

  1. Shanghai Jiao Tong University, Shanghai, China

    Xiaofeng Gao

  2. Harbin Institute of Technology, Shenzhen, China

    Hongwei Du

  3. Kennesaw State University, Kennesaw, Georgia, USA

    Meng Han

Rights and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Gargano, L., Rescigno, A.A., Vaccaro, U. (2017). Onk-Strong Conflict–Free Multicoloring. In: Gao, X., Du, H., Han, M. (eds) Combinatorial Optimization and Applications. COCOA 2017. Lecture Notes in Computer Science(), vol 10628. Springer, Cham. https://doi.org/10.1007/978-3-319-71147-8_19

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

[8]ページ先頭
©2009-2025 Movatter.jp