Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Anubhav Dhar, Soumita Hait, and Sudeshna Kolay. Efficient Algorithms for Euclidean Steiner Minimal Tree on Near-Convex Terminal Sets. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{dhar_et_al:LIPIcs.ISAAC.2023.25, author = {Dhar, Anubhav and Hait, Soumita and Kolay, Sudeshna}, title = {{Efficient Algorithms for Euclidean Steiner Minimal Tree on Near-Convex Terminal Sets}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {25:1--25:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.25}, URN = {urn:nbn:de:0030-drops-193273}, doi = {10.4230/LIPIcs.ISAAC.2023.25}, annote = {Keywords: Steiner minimal tree, Euclidean Geometry, Almost Convex point sets, FPTAS, strong NP-completeness} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, and Manaswi Paraashar. Disjointness Through the Lens of Vapnik–Chervonenkis Dimension: Sparsity and Beyond. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bhattacharya_et_al:LIPIcs.APPROX/RANDOM.2020.23, author = {Bhattacharya, Anup and Chakraborty, Sourav and Ghosh, Arijit and Mishra, Gopinath and Paraashar, Manaswi}, title = {{Disjointness Through the Lens of Vapnik–Chervonenkis Dimension: Sparsity and Beyond}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {23:1--23:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.23}, URN = {urn:nbn:de:0030-drops-126261}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.23}, annote = {Keywords: Communication complexity, VC dimension, Sparsity, and Geometric Set System} }
Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Akanksha Agrawal, Sudeshna Kolay, and Meirav Zehavi. Parameter Analysis for Guarding Terrains. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{agrawal_et_al:LIPIcs.SWAT.2020.4, author = {Agrawal, Akanksha and Kolay, Sudeshna and Zehavi, Meirav}, title = {{Parameter Analysis for Guarding Terrains}}, booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)}, pages = {4:1--4:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-150-4}, ISSN = {1868-8969}, year = {2020}, volume = {162}, editor = {Albers, Susanne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.4}, URN = {urn:nbn:de:0030-drops-122514}, doi = {10.4230/LIPIcs.SWAT.2020.4}, annote = {Keywords: Terrain Guarding, Reflex Vertices, Terrain Minima, FPT Algorithm, XP Algorithm, Kernelization} }
Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Sujoy Bhore, Paz Carmi, Sudeshna Kolay, and Meirav Zehavi. Parameterized Study of Steiner Tree on Unit Disk Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bhore_et_al:LIPIcs.SWAT.2020.13, author = {Bhore, Sujoy and Carmi, Paz and Kolay, Sudeshna and Zehavi, Meirav}, title = {{Parameterized Study of Steiner Tree on Unit Disk Graphs}}, booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)}, pages = {13:1--13:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-150-4}, ISSN = {1868-8969}, year = {2020}, volume = {162}, editor = {Albers, Susanne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.13}, URN = {urn:nbn:de:0030-drops-122607}, doi = {10.4230/LIPIcs.SWAT.2020.13}, annote = {Keywords: Unit Disk Graphs, FPT, Subexponential exact algorithms, NP-Hardness, W-Hardness} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Akanksha Agrawal, Sudeshna Kolay, Jayakrishnan Madathil, and Saket Saurabh. Parameterized Complexity Classification of Deletion to List Matrix-Partition for Low-Order Matrices. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{agrawal_et_al:LIPIcs.ISAAC.2019.41, author = {Agrawal, Akanksha and Kolay, Sudeshna and Madathil, Jayakrishnan and Saurabh, Saket}, title = {{Parameterized Complexity Classification of Deletion to List Matrix-Partition for Low-Order Matrices}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {41:1--41:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.41}, URN = {urn:nbn:de:0030-drops-115372}, doi = {10.4230/LIPIcs.ISAAC.2019.41}, annote = {Keywords: list matrix partitions, parameterized classification, Almost 2-SAT, important separators, iterative compression} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra, and Saket Saurabh. Parameterized Query Complexity of Hitting Set Using Stability of Sunflowers. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 25:1-25:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bishnu_et_al:LIPIcs.ISAAC.2018.25, author = {Bishnu, Arijit and Ghosh, Arijit and Kolay, Sudeshna and Mishra, Gopinath and Saurabh, Saket}, title = {{Parameterized Query Complexity of Hitting Set Using Stability of Sunflowers}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {25:1--25:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.25}, URN = {urn:nbn:de:0030-drops-99735}, doi = {10.4230/LIPIcs.ISAAC.2018.25}, annote = {Keywords: Query complexity, Hitting set, Parameterized complexity} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Arijit Ghosh, Sudeshna Kolay, and Gopinath Mishra. FPT Algorithms for Embedding into Low Complexity Graphic Metrics. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 35:1-35:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{ghosh_et_al:LIPIcs.ESA.2018.35, author = {Ghosh, Arijit and Kolay, Sudeshna and Mishra, Gopinath}, title = {{FPT Algorithms for Embedding into Low Complexity Graphic Metrics}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {35:1--35:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.35}, URN = {urn:nbn:de:0030-drops-94988}, doi = {10.4230/LIPIcs.ESA.2018.35}, annote = {Keywords: Metric spaces, metric embedding, FPT, dynamic programming} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Sudeshna Kolay, Fahad Panolan, and Saket Saurabh. Communication Complexity of Pairs of Graph Families with Applications. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{kolay_et_al:LIPIcs.MFCS.2017.13, author = {Kolay, Sudeshna and Panolan, Fahad and Saurabh, Saket}, title = {{Communication Complexity of Pairs of Graph Families with Applications}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {13:1--13:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.13}, URN = {urn:nbn:de:0030-drops-80849}, doi = {10.4230/LIPIcs.MFCS.2017.13}, annote = {Keywords: Communication Complexity, Separating Family, FPT algorithms} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Jean-Daniel Boissonnat, Kunal Dutta, Arijit Ghosh, and Sudeshna Kolay. Kernelization of the Subset General Position Problem in Geometry. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 25:1-25:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{boissonnat_et_al:LIPIcs.MFCS.2017.25, author = {Boissonnat, Jean-Daniel and Dutta, Kunal and Ghosh, Arijit and Kolay, Sudeshna}, title = {{Kernelization of the Subset General Position Problem in Geometry}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {25:1--25:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.25}, URN = {urn:nbn:de:0030-drops-80863}, doi = {10.4230/LIPIcs.MFCS.2017.25}, annote = {Keywords: Incidence Geometry, Kernel Lower bounds, Hyperplanes, Bounded degree polynomials} }
Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)
Pradeesha Ashok, Fedor V. Fomin, Sudeshna Kolay, Saket Saurabh, and Meirav Zehavi. Exact Algorithms for Terrain Guarding. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{ashok_et_al:LIPIcs.SoCG.2017.11, author = {Ashok, Pradeesha and Fomin, Fedor V. and Kolay, Sudeshna and Saurabh, Saket and Zehavi, Meirav}, title = {{Exact Algorithms for Terrain Guarding}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {11:1--11:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-038-5}, ISSN = {1868-8969}, year = {2017}, volume = {77}, editor = {Aronov, Boris and Katz, Matthew J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.11}, URN = {urn:nbn:de:0030-drops-71975}, doi = {10.4230/LIPIcs.SoCG.2017.11}, annote = {Keywords: Terrain Guarding, Art Gallery, Exponential-Time Algorithms} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Sudeshna Kolay, Fahad Panolan, Venkatesh Raman, and Saket Saurabh. Parameterized Algorithms on Perfect Graphs for Deletion to (r,l)-Graphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 75:1-75:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{kolay_et_al:LIPIcs.MFCS.2016.75, author = {Kolay, Sudeshna and Panolan, Fahad and Raman, Venkatesh and Saurabh, Saket}, title = {{Parameterized Algorithms on Perfect Graphs for Deletion to (r,l)-Graphs}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {75:1--75:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.75}, URN = {urn:nbn:de:0030-drops-64846}, doi = {10.4230/LIPIcs.MFCS.2016.75}, annote = {Keywords: graph deletion, FPT algorithms, polynomial kernels} }
Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)
Fedor Fomin, Sudeshna Kolay, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{fomin_et_al:LIPIcs.SoCG.2016.39, author = {Fomin, Fedor and Kolay, Sudeshna and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket}, title = {{Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems}}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, pages = {39:1--39:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-009-5}, ISSN = {1868-8969}, year = {2016}, volume = {51}, editor = {Fekete, S\'{a}ndor and Lubiw, Anna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.39}, URN = {urn:nbn:de:0030-drops-59310}, doi = {10.4230/LIPIcs.SoCG.2016.39}, annote = {Keywords: Rectilinear graphs, Steiner arborescence, parameterized algorithms} }
Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Sudeshna Kolay and Fahad Panolan. Parameterized Algorithms for Deletion to (r,ell)-Graphs. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 420-433, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{kolay_et_al:LIPIcs.FSTTCS.2015.420, author = {Kolay, Sudeshna and Panolan, Fahad}, title = {{Parameterized Algorithms for Deletion to (r,ell)-Graphs}}, booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)}, pages = {420--433}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-97-2}, ISSN = {1868-8969}, year = {2015}, volume = {45}, editor = {Harsha, Prahladh and Ramalingam, G.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.420}, URN = {urn:nbn:de:0030-drops-56456}, doi = {10.4230/LIPIcs.FSTTCS.2015.420}, annote = {Keywords: FPT, Turing kernels, Approximation algorithms} }
Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Sudeshna Kolay, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Quick but Odd Growth of Cacti. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 258-269, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{kolay_et_al:LIPIcs.IPEC.2015.258, author = {Kolay, Sudeshna and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket}, title = {{Quick but Odd Growth of Cacti}}, booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)}, pages = {258--269}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-92-7}, ISSN = {1868-8969}, year = {2015}, volume = {43}, editor = {Husfeldt, Thore and Kanj, Iyad}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.258}, URN = {urn:nbn:de:0030-drops-55883}, doi = {10.4230/LIPIcs.IPEC.2015.258}, annote = {Keywords: Even Cycle Transversal, Diamond Hitting Set, Randomized Algorithms} }
Feedback for Dagstuhl Publishing