Searching graph structures
2015/17/B/ST6/01887
Keywords
Descriptors
- ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
- ST6_4: Metody formalne, teoretyczne podstawy informatyki w tym informatyka teoretyczna
- ST1_15: Matematyczne aspekty informatyki
Panel
ST6 – Computer science and informatics: informatics and information systems, computer science, scientific computing, intelligent systems
Host institution
Politechnika Gdańska, Wydział Elektroniki, Telekomunikacji i Informatyki
Voivodeship: pomorskie
Principal investigator (from the host institution)
dr hab. Dariusz Piotr Dereniowski
Number of co-investigators in the project: 5
Call
OPUS 9 – announced on 2015-03-16
- Amount awarded
- 287 280 PLN
- Project start date
- 2016-01-27
- Project end date
- 2019-12-26
- Project duration
- 47 months (the same as in the proposal)
- Project status
- Project settled
Project description
Download the project description in a pdf file
Note — project descriptions were prepared by the authors of the applications themselves and placed in the system in an unchanged form.
Information in the final report
Publication in academic press/journals (17)
-
Searching by Heterogeneous Agents
- Authors:
- Dariusz Dereniowski, Łukasz Kuszner, Robert Ostrowski
- Academic press:
- Journal of Computer and System Sciences (year: 2021, volume: 115, pages: 46043), Publisher: Elsevier
- Status:
- Published
- DOI:
- 10.1016/j.jcss.2020.06.008 – link to the publication
-
Building a Nest by an Automaton
- Authors:
- Jurek Czyzowicz, Dariusz Dereniowski, Andrzej Pelc
- Academic press:
- Algorithmica (year: 2021, volume: 83, pages: 144-176), Publisher: Springer
- Status:
- Published
- DOI:
- 10.1007/s00453-020-00752-0 – link to the publication
-
Vertex-edge domination in cubic graphs
- Authors:
- Radosław Ziemann, Paweł Żyliński
- Academic press:
- Discrete Mathematics (year: 2020, volume: 343, pages: 112075), Publisher: Elsevier
- Status:
- Published
- DOI:
- 10.1016/j.disc.2020.112075 – link to the publication
-
A linear algorithm for connected domination in partial k-trees
- Authors:
- Radosław Ziemann
- Academic press:
- WSEAS Transaction on Mathematics (year: 2019, volume: 18, pages: 237-240), Publisher: World Scientific and Engineering Academy and Society
- Status:
- Published
-
On-line Search in Two-Dimensional Environment
- Authors:
- Dariusz Dereniowski, Dorota Osula
- Academic press:
- Theory of Computing Systems (year: 2019, volume: 63, pages: 1819-1848), Publisher: Springer
- Status:
- Published
- DOI:
- 10.1007/s00224-019-09948-6 – link to the publication
-
Vertex-edge domination in graphs
- Authors:
- Paweł Żyliński
- Academic press:
- Aequationes mathematicae (year: 2019, volume: 93, pages: 735-742), Publisher: Springer
- Status:
- Published
- DOI:
- 10.1007/s00010-018-0609-9 – link to the publication
-
Finding small-width connected path decompositions in polynomial time
- Authors:
- Dariusz Dereniowski, Dorota Osula, Paweł Rzążewski
- Academic press:
- Theoretical Computer Science (year: 2019, volume: 794, pages: 85-100), Publisher: Elsevier
- Status:
- Published
- DOI:
- 10.1016/j.tcs.2019.03.039 – link to the publication
-
Cops, a fast robber and defensive domination on interval graphs
- Authors:
- DariuszDereniowski, Tomáš Gavenčiak, Jan Kratochvíl
- Academic press:
- Theoretical Computer Science (year: 2019, volume: 794, pages: 47-58), Publisher: Elsevier
- Status:
- Published
- DOI:
- 10.1016/j.tcs.2018.09.031 – link to the publication
-
On Tradeoffs Between Width- and Fill-like Graph Parameters
- Authors:
- Dariusz Dereniowski, Adam Stański
- Academic press:
- Theory of Computing Systems (year: 2019, volume: 63, pages: 450-465), Publisher: Springer
- Status:
- Published
- DOI:
- 10.1007/s00224-019-09948-6 – link to the publication
-
Total Dominating Sets in Maximal Outerplanar Graphs
- Authors:
- Magdalena Lemańska, Rita Zuazua, Paweł Żyliński
- Academic press:
- Graphs and Combinatorics (year: 2017, volume: 33, pages: 991-998), Publisher: Springer
- Status:
- Published
- DOI:
- 10.1007/s00373-017-1802-7 – link to the publication
-
Clearing Directed Subgraphs by Mobile Agents - Variations on Covering with Paths -
- Authors:
- Dariusz Dereniowski, Andrzej Lingas, Mia Persson, Dorota Urbańska, Paweł Żyliński
- Academic press:
- Journal of Computer and System Sciences (year: 2019, volume: 102, pages: 57-68), Publisher: Elsevier
- Status:
- Published
- DOI:
- 10.1016/j.jcss.2018.11.002 – link to the publication
-
Topology recognition and leader election in colored networks
- Authors:
- D.Dereniowski, A.Pelc
- Academic press:
- Theoretical Computer Science (year: 2016, volume: 621, pages: 92-102), Publisher: Elsevier
- Status:
- Published
- DOI:
- 10.1016/j.tcs.2016.01.037 – link to the publication
-
Convex dominating sets in maximal outerplanar graphs
- Authors:
- Magdalena Lemańska, Eduardo Rivera-Campo, Radosław Ziemann, Rita Zuazua, Paweł Żyliński
- Academic press:
- Discrete Applied Mathematics (year: 2019, volume: 265, pages: 142-157), Publisher: Elsevier
- Status:
- Published
- DOI:
- 10.1016/j.dam.2019.02.029 – link to the publication
-
Graphs with equal domination and covering numbers
- Authors:
- Andrzej Lingas, Mateusz Miotk, Jerzy Topp, Paweł Żyliński
- Academic press:
- Journal of Combinatorial Optimization (year: 2020, volume: 39, pages: 55-71), Publisher: Springer
- Status:
- Published
- DOI:
- 10.1007/s10878-019-00454-6 – link to the publication
-
Reconfiguring Minimum Dominating Sets in Trees
- Authors:
- Magdalena Lemańska, Paweł Żyliński
- Academic press:
- Journal of Graph Algorithms and Applications (year: 2020, volume: 24, pages: 47-61), Publisher: Brown University (wersja elektroniczna)
- Status:
- Published
- DOI:
- 10.7155/jgaa.00517 – link to the publication
-
How to keep an eye on small things
- Authors:
- Bengt J. Nilsson, Paweł Żyliński
- Academic press:
- International Journal of Computational Geometry & Applications (year: 2020, volume: 30, pages: 97-120), Publisher: World Scientific
- Status:
- Published
- DOI:
- 10.1142/S0218195920500053 – link to the publication
-
Decontaminating Arbitrary Graphs by Mobile Agents: a Survey
- Authors:
- Dorota Osula
- Status:
- Accepted for publication
Articles in post-conference publications (12)
-
Approximation Strategies for Generalized Binary Search in Weighted Trees
- Authors:
- Dariusz Dereniowski, Adrian Kosowski, Przemyslaw Uznański, Mengchuan Zou
- Conference:
- 44th International Colloquium on Automata, Languages and Programming (year: 2017, pages: 84:1-84:14), Publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
- Date:
- conference 10-14 lipiec 2017
- Status:
- Published
-
The Snow Team Problem (Clearing Directed Subgraphs by Mobile Agents)
- Authors:
- Dariusz Dereniowski, Andrzej Lingas, Mia Persson, Dorota Urbańska, Paweł Żyliński
- Conference:
- 21st International Symposium on Fundamentals of Computation Theory, FCT 2017 (year: 2017, pages: 190-203), Publisher: Springer
- Date:
- conference 11-13 wrzesień 2017
- Status:
- Published
-
Collaborative Delivery by Energy-Sharing Low-Power Mobile Robots
- Authors:
- Evangelos Bampas, Shantanu Das, Dariusz Dereniowski, Christina Karousatou
- Conference:
- The 13th International Symposium on Algorithms and Experiments for Wireless Networks (year: 2017, pages: 46034), Publisher: Springer
- Date:
- conference 7-8 września 2017
- Status:
- Published
-
On-line Search in Two-Dimensional Environment
- Authors:
- Dariusz Dereniowski, Dorota Urbańska
- Conference:
- The 15th Workshop on Approximation and Online Algorithms (WAOA 2017) (year: 2017, pages: 223-237), Publisher: Springer
- Date:
- conference 7-8 wrzesień 2017
- Status:
- Published
-
Building a Nest by an Automaton
- Authors:
- Jurek Czyzowicz, Dariusz Dereniowski, Andrzej Pelc
- Conference:
- 27th Annual European Symposium on Algorithms, ESA 2019 (year: 2019, pages: 35:1--35:14), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
- Date:
- conference 9-11 wrzesień 2019
- Status:
- Published
-
A Framework for Searching in Graphs in the Presence of Errors
- Authors:
- Dariusz Dereniowski, Stefan Tiegel, Przemysław Uznański, Daniel Wolleb-Graf
- Conference:
- 2nd Symposium on Simplicity in Algorithms, SOSA@SODA 2019 (year: 2019, pages: 4:1--4:17), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
- Date:
- conference 8-9 styczeń 2019
- Status:
- Published
-
The lighthouse problem: Navigating by lighthouses in geometric domains
- Authors:
- Bengt J. Nilsson, Paweł Żyliński
- Conference:
- 31st Canadian Conference on Computational Geometry (year: 2019, pages: 71-77), Publisher: University of Alberta (wersja elektroniczna)
- Date:
- conference 8-10 sierpień 2019
- Status:
- Published
-
Searching by Heterogeneous Agents
- Authors:
- Dariusz Dereniowski, Łukasz Kuszner, Robert Ostrowski
- Conference:
- 11th International Conference on Algorithms and Complexity, CIAC 2019 (year: 2019, pages: 199-211), Publisher: Springer
- Date:
- conference 27-29 maj 2019
- Status:
- Published
-
Minimizing the Cost of Team Exploration
- Authors:
- Dorota Osula
- Conference:
- 45th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2019) (year: 2019, pages: 392-405), Publisher: Springer
- Date:
- conference 27-30 styczeń 2019
- Status:
- Published
-
Brief Announcement: Energy Constrained Depth First Search
- Authors:
- Shantanu Das, Dariusz Dereniowski, Przemyslaw Uznanski
- Conference:
- 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) (year: 2018, pages: 165:1-165:5), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
- Date:
- conference 9-13 lipiec 2018
- Status:
- Published
-
Generalized kernels of polygons under rotation: area and perimeter
- Authors:
- Alejandra Martínez-Moraian, David Orden, Leonidas Palios, Carlos Seara, Paweł Żyliński
- Conference:
- XVIII Spanish Meeting on Computational Geometry (year: 2019, pages: 46150), Publisher: Universitat de Girona (wersja elektroniczna)
- Date:
- conference 1-3 lipiec 2019
- Status:
- Published
-
A note on guarding staircase polygons
- Authors:
- Matt Gibson, Erik Krohn, Bengt J. Nilsson, Matthew Rayford, Paweł Żyliński
- Conference:
- 31st Canadian Conference on Computational Geometry (year: 2019, pages: 101-105), Publisher: University of Alberta (wersja elektroniczna)
- Date:
- conference 8-10 sierpień 2019
- Status:
- Published