Current Year

[1]
S. Arunachalam, S. Chakraborty, M. Koucký, N. Saurabh, and R. de Wolf, “Improved Bounds on Fourier Entropy and Min-entropy,” in 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), Montpellier, France, 2020.
Export
BibTeX
@inproceedings{Arunachalam_STACS2020, TITLE = {Improved Bounds on {Fourier} Entropy and Min-entropy}, AUTHOR = {Arunachalam, Srinivasan and Chakraborty, Sourav and Kouck{\'y}, Michal and Saurabh, Nitin and de Wolf, Ronald}, LANGUAGE = {eng}, ISSN = {1868-8969}, ISBN = {978-3-95977-140-5}, URL = {urn:nbn:de:0030-drops-119062}, DOI = {10.4230/LIPIcs.STACS.2020.45}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2020}, BOOKTITLE = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, EDITOR = {Paul, Christophe and Bl{\"a}ser, Markus}, PAGES = {1--19}, EID = {45}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {154}, ADDRESS = {Montpellier, France}, }
Endnote
%0 Conference Proceedings %A Arunachalam, Srinivasan %A Chakraborty, Sourav %A Koucký, Michal %A Saurabh, Nitin %A de Wolf, Ronald %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Improved Bounds on Fourier Entropy and Min-entropy : %G eng %U http://hdl.handle.net/21.11116/0000-0006-97AB-F %R 10.4230/LIPIcs.STACS.2020.45 %U urn:nbn:de:0030-drops-119062 %D 2020 %B 37th International Symposium on Theoretical Aspects of Computer Science %Z date of event: 2020-03-10 - 2020-03-13 %C Montpellier, France %B 37th International Symposium on Theoretical Aspects of Computer Science %E Paul, Christophe; Bläser, Markus %P 1 - 19 %Z sequence number: 45 %I Schloss Dagstuhl %@ 978-3-95977-140-5 %B Leibniz International Proceedings in Informatics %N 154 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2020/11906/
[2]
R. Becker, Y. Emek, and C. Lenzen, “Low Diameter Graph Decompositions by Approximate Distance Computation,” in 11th Innovations in Theoretical Computer Science Conference (ITICS 2020), Seattle, WA, USA, 2020.
Export
BibTeX
@inproceedings{Becker_ITCS2020, TITLE = {Low Diameter Graph Decompositions by Approximate Distance Computation}, AUTHOR = {Becker, Ruben and Emek, Yuval and Lenzen, Christoph}, LANGUAGE = {eng}, ISSN = {1868-8969}, ISBN = {978-3-95977-134-4}, URL = {urn:nbn:de:0030-drops-117355}, DOI = {10.4230/LIPIcs.ITCS.2020.50}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2020}, BOOKTITLE = {11th Innovations in Theoretical Computer Science Conference (ITICS 2020)}, EDITOR = {Vidick, Thomas}, EID = {50}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {151}, ADDRESS = {Seattle, WA, USA}, }
Endnote
%0 Conference Proceedings %A Becker, Ruben %A Emek, Yuval %A Lenzen, Christoph %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Low Diameter Graph Decompositions by Approximate Distance Computation : %G eng %U http://hdl.handle.net/21.11116/0000-0005-A7A7-2 %R 10.4230/LIPIcs.ITCS.2020.50 %U urn:nbn:de:0030-drops-117355 %D 2020 %B 11th Innovations in Theoretical Computer Science Conference %Z date of event: 2020-01-12 - 2020-01-14 %C Seattle, WA, USA %B 11th Innovations in Theoretical Computer Science Conference %E Vidick, Thomas %Z sequence number: 50 %I Schloss Dagstuhl %@ 978-3-95977-134-4 %B Leibniz International Proceedings in Informatics %N 151 %@ false %U https://drops.dagstuhl.de/opus/volltexte/2020/11735/https://drops.dagstuhl.de/doku/urheberrecht1.html
[3]
J. Bund, C. Lenzen, and M. Medina, “Optimal Metastability-Containing Sorting via Parallel Prefix Computation,” IEEE Transactions on Computers, vol. 69, no. 2, 2020.
Export
BibTeX
@article{Bund_IEEETOC2020, TITLE = {Optimal Metastability-Containing Sorting via Parallel Prefix Computation}, AUTHOR = {Bund, Johannes and Lenzen, Christoph and Medina, Moti}, LANGUAGE = {eng}, ISSN = {0018-9340}, DOI = {10.1109/TC.2019.2939818}, PUBLISHER = {IEEE}, ADDRESS = {Piscataway, NJ}, YEAR = {2020}, DATE = {2020}, JOURNAL = {IEEE Transactions on Computers}, VOLUME = {69}, NUMBER = {2}, PAGES = {198--211}, }
Endnote
%0 Journal Article %A Bund, Johannes %A Lenzen, Christoph %A Medina, Moti %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Optimal Metastability-Containing Sorting via Parallel Prefix Computation : %G eng %U http://hdl.handle.net/21.11116/0000-0005-9E7F-C %R 10.1109/TC.2019.2939818 %7 2020 %D 2020 %J IEEE Transactions on Computers %V 69 %N 2 %& 198 %P 198 - 211 %I IEEE %C Piscataway, NJ %@ false
[4]
E. Facca, A. Karrenbauer, P. Kolev, and K. Mehlhorn, “Convergence of the Non-Uniform Directed Physarum Model,” Theoretical Computer Science, vol. 816, 2020.
Export
BibTeX
@article{FaccaTCS2020, TITLE = {Convergence of the Non-Uniform Directed Physarum Model}, AUTHOR = {Facca, Enrico and Karrenbauer, Andreas and Kolev, Pavel and Mehlhorn, Kurt}, LANGUAGE = {eng}, ISSN = {0304-3975}, DOI = {10.1016/j.tcs.2020.01.034}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2020}, DATE = {2020}, JOURNAL = {Theoretical Computer Science}, VOLUME = {816}, PAGES = {184--194}, }
Endnote
%0 Journal Article %A Facca, Enrico %A Karrenbauer, Andreas %A Kolev, Pavel %A Mehlhorn, Kurt %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Convergence of the Non-Uniform Directed Physarum Model : %G eng %U http://hdl.handle.net/21.11116/0000-0006-97B9-F %R 10.1016/j.tcs.2020.01.034 %7 2020 %D 2020 %J Theoretical Computer Science %V 816 %& 184 %P 184 - 194 %I Elsevier %C Amsterdam %@ false
[5]
D. Halperin, S. Har-Peled, K. Mehlhorn, E. Oh, and M. Sharir, “The Maximum-Level Vertex in an Arrangement of Lines,” 2020. [Online]. Available: http://arxiv.org/abs/2003.00518. (arXiv: 2003.00518)
Abstract
Let $L$ be a set of $n$ lines in the plane, not necessarily in general position. We present an efficient algorithm for finding all the vertices of the arrangement $A(L)$ of maximum level, where the level of a vertex $v$ is the number of lines of $L$ that pass strictly below $v$. The problem, posed in Exercise~8.13 in de Berg etal [BCKO08], appears to be much harder than it seems, as this vertex might not be on the upper envelope of the lines. We first assume that all the lines of $L$ are distinct, and distinguish between two cases, depending on whether or not the upper envelope of $L$ contains a bounded edge. In the former case, we show that the number of lines of $L$ that pass above any maximum level vertex $v_0$ is only $O(\log n)$. In the latter case, we establish a similar property that holds after we remove some of the lines that are incident to the single vertex of the upper envelope. We present algorithms that run, in both cases, in optimal $O(n\log n)$ time. We then consider the case where the lines of $L$ are not necessarily distinct. This setup is more challenging, and the best we have is an algorithm that computes all the maximum-level vertices in time $O(n^{4/3}\log^{3}n)$. Finally, we consider a related combinatorial question for degenerate arrangements, where many lines may intersect in a single point, but all the lines are distinct: We bound the complexity of the weighted $k$-level in such an arrangement, where the weight of a vertex is the number of lines that pass through the vertex. We show that the bound in this case is $O(n^{4/3})$, which matches the corresponding bound for non-degenerate arrangements, and we use this bound in the analysis of one of our algorithms.
Export
BibTeX
@online{Halperin_arXiv2003.00518, TITLE = {The Maximum-Level Vertex in an Arrangement of Lines}, AUTHOR = {Halperin, Dan and Har-Peled, Sariel and Mehlhorn, Kurt and Oh, Eunjin and Sharir, Micha}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/2003.00518}, EPRINT = {2003.00518}, EPRINTTYPE = {arXiv}, YEAR = {2020}, ABSTRACT = {Let $L$ be a set of $n$ lines in the plane, not necessarily in general position. We present an efficient algorithm for finding all the vertices of the arrangement $A(L)$ of maximum level, where the level of a vertex $v$ is the number of lines of $L$ that pass strictly below $v$. The problem, posed in Exercise~8.13 in de Berg etal [BCKO08], appears to be much harder than it seems, as this vertex might not be on the upper envelope of the lines. We first assume that all the lines of $L$ are distinct, and distinguish between two cases, depending on whether or not the upper envelope of $L$ contains a bounded edge. In the former case, we show that the number of lines of $L$ that pass above any maximum level vertex $v_0$ is only $O(\log n)$. In the latter case, we establish a similar property that holds after we remove some of the lines that are incident to the single vertex of the upper envelope. We present algorithms that run, in both cases, in optimal $O(n\log n)$ time. We then consider the case where the lines of $L$ are not necessarily distinct. This setup is more challenging, and the best we have is an algorithm that computes all the maximum-level vertices in time $O(n^{4/3}\log^{3}n)$. Finally, we consider a related combinatorial question for degenerate arrangements, where many lines may intersect in a single point, but all the lines are distinct: We bound the complexity of the weighted $k$-level in such an arrangement, where the weight of a vertex is the number of lines that pass through the vertex. We show that the bound in this case is $O(n^{4/3})$, which matches the corresponding bound for non-degenerate arrangements, and we use this bound in the analysis of one of our algorithms.}, }
Endnote
%0 Report %A Halperin, Dan %A Har-Peled, Sariel %A Mehlhorn, Kurt %A Oh, Eunjin %A Sharir, Micha %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T The Maximum-Level Vertex in an Arrangement of Lines : %G eng %U http://hdl.handle.net/21.11116/0000-0006-AFB1-D %U http://arxiv.org/abs/2003.00518 %D 2020 %X Let $L$ be a set of $n$ lines in the plane, not necessarily in general position. We present an efficient algorithm for finding all the vertices of the arrangement $A(L)$ of maximum level, where the level of a vertex $v$ is the number of lines of $L$ that pass strictly below $v$. The problem, posed in Exercise~8.13 in de Berg etal [BCKO08], appears to be much harder than it seems, as this vertex might not be on the upper envelope of the lines. We first assume that all the lines of $L$ are distinct, and distinguish between two cases, depending on whether or not the upper envelope of $L$ contains a bounded edge. In the former case, we show that the number of lines of $L$ that pass above any maximum level vertex $v_0$ is only $O(\log n)$. In the latter case, we establish a similar property that holds after we remove some of the lines that are incident to the single vertex of the upper envelope. We present algorithms that run, in both cases, in optimal $O(n\log n)$ time. We then consider the case where the lines of $L$ are not necessarily distinct. This setup is more challenging, and the best we have is an algorithm that computes all the maximum-level vertices in time $O(n^{4/3}\log^{3}n)$. Finally, we consider a related combinatorial question for degenerate arrangements, where many lines may intersect in a single point, but all the lines are distinct: We bound the complexity of the weighted $k$-level in such an arrangement, where the weight of a vertex is the number of lines that pass through the vertex. We show that the bound in this case is $O(n^{4/3})$, which matches the corresponding bound for non-degenerate arrangements, and we use this bound in the analysis of one of our algorithms. %K Computer Science, Computational Geometry, cs.CG
[6]
P. Jain, L. Kanesh, and P. Misra, “Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized,” Theory of Computing Systems, 2020.
Export
BibTeX
@article{Jain2020, TITLE = {Conflict Free Version of Covering Problems on Graphs: {C}lassical and Parameterized}, AUTHOR = {Jain, Pallavi and Kanesh, Lawqueen and Misra, Pranabendu}, LANGUAGE = {eng}, ISSN = {1432-4350}, DOI = {10.1007/s00224-019-09964-6}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2020}, JOURNAL = {Theory of Computing Systems}, }
Endnote
%0 Journal Article %A Jain, Pallavi %A Kanesh, Lawqueen %A Misra, Pranabendu %+ External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized : %G eng %U http://hdl.handle.net/21.11116/0000-0006-90BA-5 %R 10.1007/s00224-019-09964-6 %7 2020 %D 2020 %J Theory of Computing Systems %I Springer %C New York, NY %@ false
[7]
A. Karrenbauer, P. Kolev, and K. Mehlhorn, “Convergence of the Non-Uniform Physarum Dynamics,” Theoretical Computer Science, vol. 816, 2020.
Export
BibTeX
@article{KarrenbauerTCS2020, TITLE = {Convergence of the Non-Uniform Physarum Dynamics}, AUTHOR = {Karrenbauer, Andreas and Kolev, Pavel and Mehlhorn, Kurt}, LANGUAGE = {eng}, ISSN = {0304-3975}, DOI = {10.1016/j.tcs.2020.02.032}, PUBLISHER = {Elsevier}, ADDRESS = {Amsterdam}, YEAR = {2020}, DATE = {2020}, JOURNAL = {Theoretical Computer Science}, VOLUME = {816}, PAGES = {260--269}, }
Endnote
%0 Journal Article %A Karrenbauer, Andreas %A Kolev, Pavel %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Convergence of the Non-Uniform Physarum Dynamics : %G eng %U http://hdl.handle.net/21.11116/0000-0006-97C1-5 %R 10.1016/j.tcs.2020.02.032 %7 2020 %D 2020 %J Theoretical Computer Science %V 816 %& 260 %P 260 - 269 %I Elsevier %C Amsterdam %@ false
[8]
E. Oh and H.-K. Ahn, “Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon,” Discrete & Computational Geometry, vol. 63, no. 2, 2020.
Export
BibTeX
@article{Oh2020, TITLE = {Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon}, AUTHOR = {Oh, Eunjin and Ahn, Hee-Kap}, LANGUAGE = {eng}, ISSN = {0179-5376}, DOI = {10.1007/s00454-019-00063-4}, PUBLISHER = {Springer}, YEAR = {2020}, DATE = {2020}, JOURNAL = {Discrete \& Computational Geometry}, VOLUME = {63}, NUMBER = {2}, PAGES = {418--454}, }
Endnote
%0 Journal Article %A Oh, Eunjin %A Ahn, Hee-Kap %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon : %G eng %U http://hdl.handle.net/21.11116/0000-0006-8E04-6 %R 10.1007/s00454-019-00063-4 %7 2019 %D 2020 %J Discrete & Computational Geometry %V 63 %N 2 %& 418 %P 418 - 454 %I Springer %@ false
[9]
A. Oulasvirta, N. R. Dayama, M. Shiripour, M. John, and A. Karrenbauer, “Combinatorial Optimization of Graphical User Interface Designs,” Proceedings of the IEEE, vol. 108, no. 3, 2020.
Export
BibTeX
@article{Oulasvirta2020, TITLE = {Combinatorial Optimization of Graphical User Interface Designs}, AUTHOR = {Oulasvirta, Antti and Dayama, Niraj Ramesh and Shiripour, Morteza and John, Maximilian and Karrenbauer, Andreas}, LANGUAGE = {eng}, ISSN = {0018-9219}, DOI = {10.1109/JPROC.2020.2969687}, PUBLISHER = {IEEE}, ADDRESS = {New York, N.Y.}, YEAR = {2020}, DATE = {2020}, JOURNAL = {Proceedings of the IEEE}, VOLUME = {108}, NUMBER = {3}, PAGES = {434--464}, }
Endnote
%0 Journal Article %A Oulasvirta, Antti %A Dayama, Niraj Ramesh %A Shiripour, Morteza %A John, Maximilian %A Karrenbauer, Andreas %+ External Organizations External Organizations External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Combinatorial Optimization of Graphical User Interface Designs : %G eng %U http://hdl.handle.net/21.11116/0000-0006-99BA-C %R 10.1109/JPROC.2020.2969687 %7 2020 %D 2020 %J Proceedings of the IEEE %O Proc. IEEE %V 108 %N 3 %& 434 %P 434 - 464 %I IEEE %C New York, N.Y. %@ false
[10]
B. Ray Chaudhury, J. Garg, and K. Mehlhorn, “EFX exists for three agents,” 2020. [Online]. Available: http://arxiv.org/abs/2002.05119. (arXiv: 2002.05119)
Abstract
We study the problem of distributing a set of indivisible items among agents with additive valuations in a $\mathit{fair}$ manner. The fairness notion under consideration is Envy-freeness up to any item (EFX). Despite significant efforts by many researchers for several years, the existence of EFX allocations has not been settled beyond the simple case of two agents. In this paper, we show constructively that an EFX allocation always exists for three agents. Furthermore, we falsify the conjecture by Caragiannis et al. by showing an instance with three agents for which there is a partial EFX allocation (some items are not allocated) with higher Nash welfare than that of any complete EFX allocation.
Export
BibTeX
@online{RayChaudhury_arXiv2002.05119, TITLE = {{EFX} exists for three agents}, AUTHOR = {Ray Chaudhury, Bhaskar and Garg, Jugal and Mehlhorn, Kurt}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/2002.05119}, EPRINT = {2002.05119}, EPRINTTYPE = {arXiv}, YEAR = {2020}, ABSTRACT = {We study the problem of distributing a set of indivisible items among agents with additive valuations in a $\mathit{fair}$ manner. The fairness notion under consideration is Envy-freeness up to any item (EFX). Despite significant efforts by many researchers for several years, the existence of EFX allocations has not been settled beyond the simple case of two agents. In this paper, we show constructively that an EFX allocation always exists for three agents. Furthermore, we falsify the conjecture by Caragiannis et al. by showing an instance with three agents for which there is a partial EFX allocation (some items are not allocated) with higher Nash welfare than that of any complete EFX allocation.}, }
Endnote
%0 Report %A Ray Chaudhury, Bhaskar %A Garg, Jugal %A Mehlhorn, Kurt %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society Algorithms and Complexity, MPI for Informatics, Max Planck Society %T EFX exists for three agents : %G eng %U http://hdl.handle.net/21.11116/0000-0006-AF99-9 %U http://arxiv.org/abs/2002.05119 %D 2020 %X We study the problem of distributing a set of indivisible items among agents with additive valuations in a $\mathit{fair}$ manner. The fairness notion under consideration is Envy-freeness up to any item (EFX). Despite significant efforts by many researchers for several years, the existence of EFX allocations has not been settled beyond the simple case of two agents. In this paper, we show constructively that an EFX allocation always exists for three agents. Furthermore, we falsify the conjecture by Caragiannis et al. by showing an instance with three agents for which there is a partial EFX allocation (some items are not allocated) with higher Nash welfare than that of any complete EFX allocation. %K Computer Science, Computer Science and Game Theory, cs.GT,
[11]
B. Ray Chaudhury, T. Kavitha, K. Mehlhorn, and A. Sgouritsa, “A Little Charity Guarantees Almost Envy-Freeness,” in Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), Salt Lake City, UT, USA, 2020.
Export
BibTeX
@inproceedings{RayChaudhury_SODA20, TITLE = {A Little Charity Guarantees Almost Envy-Freeness}, AUTHOR = {Ray Chaudhury, Bhaskar and Kavitha, Telikepalli and Mehlhorn, Kurt and Sgouritsa, Alkmini}, LANGUAGE = {eng}, ISBN = {978-1-61197-599-4}, DOI = {10.1137/1.9781611975994.162}, PUBLISHER = {SIAM}, YEAR = {2020}, BOOKTITLE = {Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms (SODA 2020)}, EDITOR = {Chawla, Shuchi}, PAGES = {2658 --2672}, ADDRESS = {Salt Lake City, UT, USA}, }
Endnote
%0 Conference Proceedings %A Ray Chaudhury, Bhaskar %A Kavitha, Telikepalli %A Mehlhorn, Kurt %A Sgouritsa, Alkmini %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations %T A Little Charity Guarantees Almost Envy-Freeness : %G eng %U http://hdl.handle.net/21.11116/0000-0006-AF89-B %R 10.1137/1.9781611975994.162 %D 2020 %B 31st Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2020-01-05 - 2020-01-08 %C Salt Lake City, UT, USA %B Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms %E Chawla, Shuchi %P 2658 - 2672 %I SIAM %@ 978-1-61197-599-4
[12]
M. Roth and P. Wellnitz, “Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory,” in Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), Salt Lake City, UT, USA, 2020.
Export
BibTeX
@inproceedings{Roth_SODA20, TITLE = {Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory}, AUTHOR = {Roth, Marc and Wellnitz, Philip}, LANGUAGE = {eng}, ISBN = {978-1-61197-599-4}, DOI = {10.1137/1.9781611975994.133}, PUBLISHER = {SIAM}, YEAR = {2020}, BOOKTITLE = {Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms (SODA 2020)}, EDITOR = {Chawla, Shuchi}, PAGES = {2161--2180}, ADDRESS = {Salt Lake City, UT, USA}, }
Endnote
%0 Conference Proceedings %A Roth, Marc %A Wellnitz, Philip %+ External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory : %G eng %U http://hdl.handle.net/21.11116/0000-0005-8665-2 %R 10.1137/1.9781611975994.133 %D 2020 %B 31st Annual ACM-SIAM Symposium on Discrete Algorithms %Z date of event: 2020-01-05 - 2020-01-08 %C Salt Lake City, UT, USA %B Proceedings of the Thirty-First ACM-SIAM Symposium on Discrete Algorithms %E Chawla, Shuchi %P 2161 - 2180 %I SIAM %@ 978-1-61197-599-4
[13]
S. Saurabh, U. dos S. Souza, and P. Tale, “On the Parameterized Complexity of Grid Contraction,” in 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020), órshavn, Faroe Islands, 2020.
Export
BibTeX
@inproceedings{Saket_SWAT2020, TITLE = {On the Parameterized Complexity of Grid Contraction}, AUTHOR = {Saurabh, Saket and Souza, U{\'e}verton dos Santos and Tale, Prafullkumar}, LANGUAGE = {eng}, ISBN = {978-3-95977-150-4}, URL = {urn:nbn:de:0030-drops-122810}, DOI = {10.4230/LIPIcs.SWAT.2020.34}, PUBLISHER = {Schloss Dagstuhl}, YEAR = {2020}, BOOKTITLE = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)}, EDITOR = {Albers, Susanne}, EID = {34}, SERIES = {Leibniz International Proceedings in Informatics}, VOLUME = {162}, ADDRESS = {{\'o}rshavn, Faroe Islands}, }
Endnote
%0 Conference Proceedings %A Saurabh, Saket %A Souza, Uéverton dos Santos %A Tale, Prafullkumar %+ Algorithms and Complexity, MPI for Informatics, Max Planck Society External Organizations Algorithms and Complexity, MPI for Informatics, Max Planck Society %T On the Parameterized Complexity of Grid Contraction : %G eng %U http://hdl.handle.net/21.11116/0000-0006-8BA6-2 %R 10.4230/LIPIcs.SWAT.2020.34 %U urn:nbn:de:0030-drops-122810 %D 2020 %B 17th Scandinavian Symposiumand Workshops on Algorithm Theory %Z date of event: 2020-06-22 - 2020-06-24 %C órshavn, Faroe Islands %B 17th Scandinavian Symposium and Workshops on Algorithm Theory %E Albers, Susanne %Z sequence number: 34 %I Schloss Dagstuhl %@ 978-3-95977-150-4 %B Leibniz International Proceedings in Informatics %N 162 %U https://drops.dagstuhl.de/opus/volltexte/2020/12281/