Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Searching graph structures

2015/17/B/ST6/01887

Keywords:

graph searching optimization algorithms computational complexity

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory
  • ST6_4: Formal methods, foundations of computer science, including theoretical computer science, quantum algorithms
  • ST1_15: Mathematical aspects of computer science

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

woj. pomorskie

Other projects carried out by the institution 

Principal investigator (from the host institution):

dr hab. Dariusz 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 (Y-m-d): 2016-01-27

Project end date (Y-m-d): 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 (18)
  • Articles in post-conference publications (12)
  1. Building a Nest by an Automaton
    Authors:
    Jurek Czyzowicz, Dariusz Dereniowski, Andrzej Pelc
    Academic press:
    Algorithmica (rok: 2021, tom: 83, strony: 144-176), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-020-00752-0 - link to the publication
  2. Reconfiguring Minimum Dominating Sets in Trees
    Authors:
    Magdalena Lemańska, Paweł Żyliński
    Academic press:
    Journal of Graph Algorithms and Applications (rok: 2020, tom: 24, strony: 47-61), Wydawca: Brown University (wersja elektroniczna)
    Status:
    Published
    DOI:
    10.7155/jgaa.00517 - link to the publication
  3. 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 (rok: 2019, tom: 265, strony: 142-157), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.dam.2019.02.029 - link to the publication
  4. On Tradeoffs Between Width- and Fill-like Graph Parameters
    Authors:
    Dariusz Dereniowski, Adam Stański
    Academic press:
    Theory of Computing Systems (rok: 2019, tom: 63, strony: 450-465), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00224-019-09948-6 - link to the publication
  5. Topology recognition and leader election in colored networks
    Authors:
    D.Dereniowski, A.Pelc
    Academic press:
    Theoretical Computer Science (rok: 2016, tom: 621, strony: 92-102), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2016.01.037 - link to the publication
  6. Vertex-edge domination in cubic graphs
    Authors:
    Radosław Ziemann, Paweł Żyliński
    Academic press:
    Discrete Mathematics (rok: 2020, tom: 343, strony: 112075), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.disc.2020.112075 - link to the publication
  7. Vertex-edge domination in graphs
    Authors:
    Paweł Żyliński
    Academic press:
    Aequationes mathematicae (rok: 2019, tom: 93, strony: 735-742), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00010-018-0609-9 - link to the publication
  8. Decontaminating Arbitrary Graphs by Mobile Agents: a Survey
    Authors:
    Dorota Osula
    Academic press:
    Utilitas Mathematica , Wydawca: Utilitas Mathematica Publishing Inc. Winnipeg, Manitoba, Canada
    Status:
    Accepted for publication
    DOI:
    brak - link to the publication
  9. Finding small-width connected path decompositions in polynomial time
    Authors:
    Dariusz Dereniowski, Dorota Osula, Paweł Rzążewski
    Academic press:
    Theoretical Computer Science (rok: 2019, tom: 794, strony: 85-100), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2019.03.039 - link to the publication
  10. Total Dominating Sets in Maximal Outerplanar Graphs
    Authors:
    Magdalena Lemańska, Rita Zuazua, Paweł Żyliński
    Academic press:
    Graphs and Combinatorics (rok: 2017, tom: 33, strony: 991-998), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00373-017-1802-7 - link to the publication
  11. Cops, a fast robber and defensive domination on interval graphs
    Authors:
    DariuszDereniowski, Tomáš Gavenčiak, Jan Kratochvíl
    Academic press:
    Theoretical Computer Science (rok: 2019, tom: 794, strony: 47-58), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2018.09.031 - link to the publication
  12. A linear algorithm for connected domination in partial k-trees
    Authors:
    Radosław Ziemann
    Academic press:
    WSEAS Transaction on Mathematics (rok: 2019, tom: 18, strony: 237-240), Wydawca: World Scientific and Engineering Academy and Society
    Status:
    Published
    DOI:
    brak - link to the publication
  13. 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 (rok: 2019, tom: 102, strony: 57-68), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.jcss.2018.11.002 - link to the publication
  14. Graphs with equal domination and covering numbers
    Authors:
    Andrzej Lingas, Mateusz Miotk, Jerzy Topp, Paweł Żyliński
    Academic press:
    Journal of Combinatorial Optimization (rok: 2020, tom: 39, strony: 55-71), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s10878-019-00454-6 - link to the publication
  15. How to keep an eye on small things
    Authors:
    Bengt J. Nilsson, Paweł Żyliński
    Academic press:
    International Journal of Computational Geometry & Applications (rok: 2020, tom: 30, strony: 97-120), Wydawca: World Scientific
    Status:
    Published
    DOI:
    10.1142/S0218195920500053 - link to the publication
  16. On-line Search in Two-Dimensional Environment
    Authors:
    Dariusz Dereniowski, Dorota Osula
    Academic press:
    Theory of Computing Systems (rok: 2019, tom: 63, strony: 1819-1848), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00224-019-09948-6 - link to the publication
  17. Searching by Heterogeneous Agents
    Authors:
    Dariusz Dereniowski, Łukasz Kuszner, Robert Ostrowski
    Academic press:
    Journal of Computer and System Sciences (rok: 2021, tom: 115, strony: 45312), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.jcss.2020.06.008 - link to the publication
  18. Energy Constrained Depth First Search
    Authors:
    Shantanu Das, Dariusz Dereniowski, Przemysław Uznański
    Academic press:
    Algorithmica , Wydawca: Springer
    Status:
    Submitted
    DOI:
    brak - link to the publication
  1. 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 (rok: 2019, ), Wydawca: University of Alberta (wersja elektroniczna)
    Data:
    konferencja 8-10 sierpień 2019
    Status:
    Published
  2. 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) (rok: 2018, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 9-13 lipiec 2018
    Status:
    Published
  3. 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) (rok: 2019, ), Wydawca: Springer
    Data:
    konferencja 27-30 styczeń 2019
    Status:
    Published
  4. The lighthouse problem: Navigating by lighthouses in geometric domains
    Authors:
    Bengt J. Nilsson, Paweł Żyliński
    Conference:
    31st Canadian Conference on Computational Geometry (rok: 2019, ), Wydawca: University of Alberta (wersja elektroniczna)
    Data:
    konferencja 8-10 sierpień 2019
    Status:
    Published
  5. 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 (rok: 2017, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 10-14 lipiec 2017
    Status:
    Published
  6. Building a Nest by an Automaton
    Authors:
    Jurek Czyzowicz, Dariusz Dereniowski, Andrzej Pelc
    Conference:
    27th Annual European Symposium on Algorithms, ESA 2019 (rok: 2019, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 9-11 wrzesień 2019
    Status:
    Published
  7. 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 (rok: 2019, ), Wydawca: Universitat de Girona (wersja elektroniczna)
    Data:
    konferencja 1-3 lipiec 2019
    Status:
    Published
  8. 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 (rok: 2019, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 8-9 styczeń 2019
    Status:
    Published
  9. 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 (rok: 2017, ), Wydawca: Springer
    Data:
    konferencja 7-8 września 2017
    Status:
    Published
  10. 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 (rok: 2017, ), Wydawca: Springer
    Data:
    konferencja 11-13 wrzesień 2017
    Status:
    Published
  11. On-line Search in Two-Dimensional Environment
    Authors:
    Dariusz Dereniowski, Dorota Urbańska
    Conference:
    The 15th Workshop on Approximation and Online Algorithms (WAOA 2017) (rok: 2017, ), Wydawca: Springer
    Data:
    konferencja 7-8 wrzesień 2017
    Status:
    Published
  12. Searching by Heterogeneous Agents
    Authors:
    Dariusz Dereniowski, Łukasz Kuszner, Robert Ostrowski
    Conference:
    11th International Conference on Algorithms and Complexity, CIAC 2019 (rok: 2019, ), Wydawca: Springer
    Data:
    konferencja 27-29 maj 2019
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy