Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Dariusz Dereniowski and Izajasz Wrosz. Constant-Factor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 42:1-42:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{dereniowski_et_al:LIPIcs.MFCS.2022.42, author = {Dereniowski, Dariusz and Wrosz, Izajasz}, title = {{Constant-Factor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {42:1--42:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.42}, URN = {urn:nbn:de:0030-drops-168405}, doi = {10.4230/LIPIcs.MFCS.2022.42}, annote = {Keywords: binary search, graph search, approximation algorithm, query complexity} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Junhao Gan, Anthony Wirth, and Xin Zhang. An Almost Optimal Algorithm for Unbounded Search with Noisy Information. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{gan_et_al:LIPIcs.SWAT.2022.25, author = {Gan, Junhao and Wirth, Anthony and Zhang, Xin}, title = {{An Almost Optimal Algorithm for Unbounded Search with Noisy Information}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {25:1--25:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.25}, URN = {urn:nbn:de:0030-drops-161854}, doi = {10.4230/LIPIcs.SWAT.2022.25}, annote = {Keywords: Fault-tolerant search, noisy binary search, query complexity} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Jurek Czyzowicz, Dariusz Dereniowski, and Andrzej Pelc. Building a Nest by an Automaton. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 35:1-35:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{czyzowicz_et_al:LIPIcs.ESA.2019.35, author = {Czyzowicz, Jurek and Dereniowski, Dariusz and Pelc, Andrzej}, title = {{Building a Nest by an Automaton}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {35:1--35:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola 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.2019.35}, URN = {urn:nbn:de:0030-drops-111564}, doi = {10.4230/LIPIcs.ESA.2019.35}, annote = {Keywords: finite automaton, plane, grid, construction task, brick, mobile agent, robot} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Dariusz Dereniowski, Stefan Tiegel, Przemyslaw Uznanski, and Daniel Wolleb-Graf. A Framework for Searching in Graphs in the Presence of Errors. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dereniowski_et_al:OASIcs.SOSA.2019.4, author = {Dereniowski, Dariusz and Tiegel, Stefan and Uznanski, Przemyslaw and Wolleb-Graf, Daniel}, title = {{A Framework for Searching in Graphs in the Presence of Errors}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {4:1--4:17}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-099-6}, ISSN = {2190-6807}, year = {2019}, volume = {69}, editor = {Fineman, Jeremy T. and Mitzenmacher, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.4}, URN = {urn:nbn:de:0030-drops-100305}, doi = {10.4230/OASIcs.SOSA.2019.4}, annote = {Keywords: graph algorithms, noisy binary search, query complexity, reliability} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Shantanu Das, Dariusz Dereniowski, and Przemyslaw Uznanski. Brief Announcement: Energy Constrained Depth First Search. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 165:1-165:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{das_et_al:LIPIcs.ICALP.2018.165, author = {Das, Shantanu and Dereniowski, Dariusz and Uznanski, Przemyslaw}, title = {{Brief Announcement: Energy Constrained Depth First Search}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {165:1--165:5}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.165}, URN = {urn:nbn:de:0030-drops-91693}, doi = {10.4230/LIPIcs.ICALP.2018.165}, annote = {Keywords: DFS traversal, distributed algorithm, graph exploration, piecemeal exploration, online exploration} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Dariusz Dereniowski, Adrian Kosowski, Przemyslaw Uznanski, and Mengchuan Zou. Approximation Strategies for Generalized Binary Search in Weighted Trees. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 84:1-84:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{dereniowski_et_al:LIPIcs.ICALP.2017.84, author = {Dereniowski, Dariusz and Kosowski, Adrian and Uznanski, Przemyslaw and Zou, Mengchuan}, title = {{Approximation Strategies for Generalized Binary Search in Weighted Trees}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {84:1--84:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.84}, URN = {urn:nbn:de:0030-drops-74507}, doi = {10.4230/LIPIcs.ICALP.2017.84}, annote = {Keywords: Approximation Algorithm, Adaptive Algorithm, Graph Search, Binary Search, Vertex Ranking, Trees} }
Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Dariusz Dereniowski, Adrian Kosowski, Dominik Pajak, and Przemyslaw Uznanski. Bounds on the Cover Time of Parallel Rotor Walks. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 263-275, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{dereniowski_et_al:LIPIcs.STACS.2014.263, author = {Dereniowski, Dariusz and Kosowski, Adrian and Pajak, Dominik and Uznanski, Przemyslaw}, title = {{Bounds on the Cover Time of Parallel Rotor Walks}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {263--275}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.263}, URN = {urn:nbn:de:0030-drops-44637}, doi = {10.4230/LIPIcs.STACS.2014.263}, annote = {Keywords: Distributed graph exploration, Rotor-Router, Collaborative robots, Parallel random walks, Derandomization} }
Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Dariusz Dereniowski. From Pathwidth to Connected Pathwidth. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 416-427, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
@InProceedings{dereniowski:LIPIcs.STACS.2011.416, author = {Dereniowski, Dariusz}, title = {{From Pathwidth to Connected Pathwidth}}, booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, pages = {416--427}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-25-5}, ISSN = {1868-8969}, year = {2011}, volume = {9}, editor = {Schwentick, Thomas and D\"{u}rr, Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.416}, URN = {urn:nbn:de:0030-drops-30311}, doi = {10.4230/LIPIcs.STACS.2011.416}, annote = {Keywords: connected pathwidth, connected searching, fugitive search games, graph searching, pathwidth} }
Feedback for Dagstuhl Publishing