Document Open Access Logo

Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth

Author Michał Włodarczyk

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.106.pdf
  • Filesize: 1.13 MB
  • 20 pages

Document Identifiers

Author Details

Michał Włodarczyk
  • Ben-Gurion University, Beer Sheva, Israel

Funding

Supported by the European Research Council (ERC) grant titled PARAPATH. Part of the work has been carried out when the author was a postdoctorate student at the Eindhoven University of Technology.

Cite AsGet BibTex

Michał Włodarczyk. Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 106:1-106:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ICALP.2023.106

Abstract

In Chordal/Interval Vertex Deletion we ask how many vertices one needs to remove from a graph to make it chordal (respectively: interval). We study these problems under the parameterization by treewidth tw of the input graph G. On the one hand, we present an algorithm for Chordal Vertex Deletion with running time 2^𝒪(tw)⋅|V(G)|, improving upon the running time 2^𝒪(tw²)⋅|V(G)|^𝒪(1) by Jansen, de Kroon, and Włodarczyk (STOC'21). When a tree decomposition of width tw is given, then the base of the exponent equals 2^{ω-1}⋅3 + 1. Our algorithm is based on a novel link between chordal graphs and graphic matroids, which allows us to employ the framework of representative families. On the other hand, we prove that the known 2^𝒪(tw log tw)⋅|V(G)|-time algorithm for Interval Vertex Deletion cannot be improved assuming Exponential Time Hypothesis.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • fixed-parameter tractability
  • treewidth
  • chordal graphs
  • interval graphs
  • matroids
  • representative families

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Akanksha Agrawal, Sudeshna Kolay, Daniel Lokshtanov, and Saket Saurabh. A faster FPT algorithm and a smaller kernel for block graph vertex deletion. In Evangelos Kranakis, Gonzalo Navarro, and Edgar Chávez, editors, LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings, volume 9644 of Lecture Notes in Computer Science, pages 1-13. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-49529-2_1.
  2. Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. Erdös-Pósa property of obstructions to interval graphs. In Rolf Niedermeier and Brigitte Vallée, editors, 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, volume 96 of LIPIcs, pages 7:1-7:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.7.
  3. Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. Feedback vertex set inspired kernel for chordal vertex deletion. ACM Trans. Algorithms, 15(1):11:1-11:28, 2019. URL: https://doi.org/10.1145/3284356.
  4. Akanksha Agrawal, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. Interval vertex deletion admits a polynomial kernel. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '19, pages 1711-1730, USA, 2019. Society for Industrial and Applied Mathematics. URL: https://doi.org/10.1137/1.9781611975482.103.
  5. Jungho Ahn, Eduard Eiben, O joung Kwon, and Sang il Oum. A Polynomial Kernel for 3-Leaf Power Deletion. In Javier Esparza and Daniel Kráľ, editors, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1-5:14, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.5.
  6. Jungho Ahn, Eun Jung Kim, and Euiwoong Lee. Towards constant-factor approximation for chordal/distance-hereditary vertex deletion. Algorithmica, 84(7):2106-2133, 2022. URL: https://doi.org/10.1007/s00453-022-00963-7.
  7. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '21, pages 522-539, USA, 2021. Society for Industrial and Applied Mathematics. URL: https://doi.org/10.5555/3458064.3458096.
  8. Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph (Seffi) Naor, and Baruch Schieber. A unified approach to approximating resource allocation and scheduling. J. ACM, 48(5):1069-1090, September 2001. URL: https://doi.org/10.1145/502102.502107.
  9. Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 951-970. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.57.
  10. Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. Hitting minors on bounded treewidth graphs. I. General upper bounds. SIAM J. Discret. Math., 34(3):1623-1648, 2020. URL: https://doi.org/10.1137/19M1287146.
  11. Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms. Theor. Comput. Sci., 814:135-152, 2020. URL: https://doi.org/10.1016/j.tcs.2020.01.026.
  12. Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. Hitting minors on bounded treewidth graphs. III. Lower bounds. J. Comput. Syst. Sci., 109:56-77, 2020. URL: https://doi.org/10.1016/j.jcss.2019.11.002.
  13. Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall PTR, USA, 1st edition, 1998. URL: https://dl.acm.org/doi/10.5555/551884.
  14. Seymour Benzer. On the topology of the genetic fine structure. Proceedings of the National Academy of Sciences of the United States of America, 45(11):1607-1620, 1959. URL: http://www.jstor.org/stable/90127.
  15. Benjamin Bergougnoux, Édouard Bonnet, Nick Brettell, and O joung Kwon. Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth. In Yixin Cao and Marcin Pilipczuk, editors, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), volume 180 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1-3:17, 2020. URL: https://doi.org/10.4230/LIPIcs.IPEC.2020.3.
  16. Jean R. S. Blair and Barry Peyton. An introduction to chordal graphs and clique trees. In Alan George, John R. Gilbert, and Joseph W. H. Liu, editors, Graph Theory and Sparse Matrix Computation, pages 1-29, New York, NY, 1993. Springer New York. Google Scholar
  17. Ivan Bliznets, Marek Cygan, Pawel Komosa, Michal Pilipczuk, and Lukás Mach. Lower bounds for the parameterized complexity of minimum fill-in and other completion problems. ACM Trans. Algorithms, 16(2):25:1-25:31, 2020. URL: https://doi.org/10.1145/3381426.
  18. Ivan Bliznets, Fedor V Fomin, Michał Pilipczuk, and Yngve Villanger. Largest chordal and interval subgraphs faster than 2ⁿ. Algorithmica, 76(2):569-594, 2016. Google Scholar
  19. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput., 243:86-111, 2015. URL: https://doi.org/10.1016/j.ic.2014.12.008.
  20. Hans L. Bodlaender, Pål Gronås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michał Pilipczuk. A c^k n 5-approximation algorithm for treewidth. SIAM Journal on Computing, 45(2):317-378, 2016. URL: https://doi.org/10.1137/130947374.
  21. Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. (Meta) Kernelization. J. ACM, 63(5):44:1-44:69, 2016. URL: https://doi.org/10.1145/2973749.
  22. Marthe Bonamy, Lukasz Kowalik, Jesper Nederlof, Michal Pilipczuk, Arkadiusz Socala, and Marcin Wrochna. On directed feedback vertex set parameterized by treewidth. In Andreas Brandstädt, Ekkehard Köhler, and Klaus Meer, editors, Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings, volume 11159 of Lecture Notes in Computer Science, pages 65-78. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-00256-5_6.
  23. Édouard Bonnet, Nick Brettell, O joung Kwon, and Dániel Marx. Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms. In Daniel Lokshtanov and Naomi Nishimura, editors, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), volume 89 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1-7:13, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.IPEC.2017.7.
  24. Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad. Graph classes: a survey. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1999. URL: https://doi.org/10.1137/1.9780898719796.
  25. Peter Buneman. A characterisation of rigid circuit graphs. Discrete Math., 9(3):205-212, September 1974. URL: https://doi.org/10.1016/0012-365X(74)90002-8.
  26. Leizhen Cai. Parameterized complexity of vertex colouring. Discrete Applied Mathematics, 127(3):415-429, 2003. URL: https://doi.org/10.1016/S0166-218X(02)00242-1.
  27. Yixin Cao. Linear recognition of almost interval graphs. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1096-1115. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch77.
  28. Yixin Cao and Dániel Marx. Interval deletion is fixed-parameter tractable. ACM Trans. Algorithms, 11(3), January 2015. URL: https://doi.org/10.1145/2629595.
  29. Yixin Cao and Dániel Marx. Chordal editing is fixed-parameter tractable. Algorithmica, 75(1):118-137, May 2016. URL: https://doi.org/10.1007/s00453-015-0014-x.
  30. Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach, volume 138 of Encyclopedia of mathematics and its applications. Cambridge University Press, 2012. URL: https://doi.org/10.1017/CBO9780511977619.
  31. Radu Curticapea, Nathan Lindzey, and Jesper Nederlof. A tight lower bound for counting hamiltonian cycles via matrix rank. In Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1080-1099, 2018. URL: https://doi.org/10.1137/1.9781611975031.70.
  32. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  33. Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast hamiltonicity checking via bases of perfect matchings. J. ACM, 65(3):12:1-12:46, 2018. URL: https://doi.org/10.1145/3148227.
  34. Marek Cygan, Dániel Marx, Marcin Pilipczuk, and Michał Pilipczuk. Hitting forbidden subgraphs in graphs of bounded treewidth. Information and Computation, 256:62-82, 2017. URL: https://doi.org/10.1016/j.ic.2017.04.009.
  35. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan M. M. Van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. ACM Trans. Algorithms, 18(2), March 2022. URL: https://doi.org/10.1145/3506707.
  36. Erik D. Demaine and MohammadTaghi Hajiaghayi. The bidimensionality theory and its algorithmic applications. The Computer Journal, 51(3):292-302, 2008. URL: https://doi.org/10.1093/comjnl/bxm033.
  37. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Representative sets of product families. In Andreas S. Schulz and Dorothea Wagner, editors, Algorithms - ESA 2014, pages 443-454, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-662-44777-2_37.
  38. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM, 63(4):29:1-29:60, 2016. URL: https://doi.org/10.1145/2886094.
  39. Fedor V. Fomin and Yngve Villanger. Subexponential parameterized algorithm for minimum fill-in. SIAM Journal on Computing, 42(6):2197-2216, 2013. URL: https://doi.org/10.1137/11085390X.
  40. Fǎnicǎ Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B, 16(1):47-56, 1974. URL: https://doi.org/10.1016/0095-8956(74)90094-X.
  41. Pinar Heggernes, Pim van ’t Hof, Bart M.P. Jansen, Stefan Kratsch, and Yngve Villanger. Parameterized complexity of vertex deletion into perfect graph classes. Theoretical Computer Science, 511:172-180, 2013. Exact and Parameterized Computation. URL: https://doi.org/10.1016/j.tcs.2012.03.013.
  42. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  43. Ashwin Jacob, Fahad Panolan, Venkatesh Raman, and Vibha Sahlot. Structural parameterizations with modulator oblivion. In Yixin Cao and Marcin Pilipczuk, editors, 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 180 of LIPIcs, pages 19:1-19:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.IPEC.2020.19.
  44. Hugo Jacob, Thomas Bellitto, Oscar Defrain, and Marcin Pilipczuk. Close Relatives (Of Feedback Vertex Set), Revisited. In Petr A. Golovach and Meirav Zehavi, editors, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), volume 214 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1-21:15, Dagstuhl, Germany, 2021. URL: https://doi.org/10.4230/LIPIcs.IPEC.2021.21.
  45. Bart M. P. Jansen, Jari J. H. de Kroon, and Michał Włodarczyk. Vertex deletion parameterized by elimination distance and even less. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pages 1757-1769, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3406325.3451068.
  46. Bart M. P. Jansen, Jari J. H. de Kroon, and Michal Wlodarczyk. Vertex deletion parameterized by elimination distance and even less. CoRR, abs/2103.09715, 2021. URL: https://arxiv.org/abs/2103.09715v4.
  47. Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. A near-optimal planarization algorithm. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1802-1811. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.130.
  48. Bart M. P. Jansen and Marcin Pilipczuk. Approximation and kernelization for chordal vertex deletion. SIAM J. Discret. Math., 32(3):2258-2301, 2018. URL: https://doi.org/10.1137/17M112035X.
  49. J.Mark Keil. Finding hamiltonian circuits in interval graphs. Information Processing Letters, 20(4):201-206, 1985. URL: https://doi.org/10.1016/0020-0190(85)90050-X.
  50. David Kendall. Incidence matrices, interval graphs and seriation in archeology. Pacific Journal of mathematics, 28(3):565-570, 1969. Google Scholar
  51. Eun Jung Kim and O-joung Kwon. Erdős-Pósa property of chordless cycles and its applications. J. Comb. Theory, Ser. B, 145:65-112, 2020. URL: https://doi.org/10.1016/j.jctb.2020.05.002.
  52. Lefteris M. Kirousis and Christos H. Papadimitriou. Interval graphs and searching. Discrete Mathematics, 55(2):181-184, 1985. URL: https://doi.org/10.1016/0012-365X(85)90046-9.
  53. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algorithms, 14(2), April 2018. URL: https://doi.org/10.1145/3170442.
  54. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Slightly superexponential parameterized problems. SIAM J. Comput., 47(3):675-702, 2018. URL: https://doi.org/10.1137/16M1104834.
  55. Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. On the hardness of eliminating small induced subgraphs by contracting edges. In Gregory Z. Gutin and Stefan Szeider, editors, Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, volume 8246 of Lecture Notes in Computer Science, pages 243-254. Springer, 2013. URL: https://doi.org/10.1007/978-3-319-03898-8_21.
  56. Dániel Marx. Four shorts stories on surprising algorithmic uses of treewidth. In Fedor V. Fomin, Stefan Kratsch, and Erik Jan van Leeuwen, editors, Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday, volume 12160 of Lecture Notes in Computer Science, pages 129-144. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-42071-0_10.
  57. Dániel Marx, Barry O'Sullivan, and Igor Razgon. Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithms, 9(4):30:1-30:35, 2013. URL: https://doi.org/10.1145/2500119.
  58. Marcin Pilipczuk. A tight lower bound for vertex planarization on graphs of bounded treewidth. Discret. Appl. Math., 231:211-216, 2017. URL: https://doi.org/10.1016/j.dam.2016.05.019.
  59. Michał Pilipczuk. Problems parameterized by treewidth tractable in single exponential time: A logical approach. In Filip Murlak and Piotr Sankowski, editors, Mathematical Foundations of Computer Science 2011, pages 520-531, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-642-22993-0_47.
  60. R. C. Prim. Shortest connection networks and some generalizations. The Bell System Technical Journal, 36(6):1389-1401, 1957. URL: https://doi.org/10.1002/j.1538-7305.1957.tb01515.x.
  61. N. Robertson and P.D. Seymour. Graph minors XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B, 63(1):65-110, 1995. URL: https://doi.org/10.1006/jctb.1995.1006.
  62. Neil Robertson and P.D Seymour. Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7(3):309-322, 1986. URL: https://doi.org/10.1016/0196-6774(86)90023-4.
  63. Donald J Rose. A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In Graph theory and computing, pages 183-217. Elsevier, 1972. Google Scholar
  64. Toshiki Saitoh, Ryo Yoshinaka, and Hans L. Bodlaender. Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes. In Ryuhei Uehara, Seok-Hee Hong, and Subhas C. Nandy, editors, WALCOM: Algorithms and Computation - 15th International Conference and Workshops, 2021, Yangon, Myanmar, volume 12635 of Lecture Notes in Computer Science, pages 142-153. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-68211-8_12.
  65. Ignasi Sau and Uéverton dos Santos Souza. Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs. In Javier Esparza and Daniel Kráľ, editors, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 82:1-82:15, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.82.
  66. Hadas Shachnai and Meirav Zehavi. Representative families: A unified tradeoff-based approach. Journal of Computer and System Sciences, 82(3):488-502, 2016. URL: https://doi.org/10.1016/j.jcss.2015.11.008.
  67. Johan MM Van Rooij, Hans L Bodlaender, and Peter Rossmanith. Dynamic programming on tree decompositions using generalised fast subset convolution. In European Symposium on Algorithms, pages 566-577. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-04128-0_51.
  68. Pim van 't Hof and Yngve Villanger. Proper interval vertex deletion. Algorithmica, 65(4):845-867, 2013. URL: https://doi.org/10.1007/s00453-012-9661-3.
  69. Michał Włodarczyk. Clifford algebras meet tree decompositions. Algorithmica, 81(2):497-518, 2019. URL: https://doi.org/10.1007/s00453-018-0489-3.
  70. Mihalis Yannakakis. Computing the minimum fill-in is NP-complete. SIAM Journal on Algebraic Discrete Methods, 2(1):77-79, 1981. URL: https://doi.org/10.1137/0602010.
  71. Meirav Zehavi. Mixing color coding-related techniques. In Algorithms-ESA 2015, pages 1037-1049. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_86.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact