Projekty finansowane przez NCN

Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Przeszukiwanie struktur grafowych

2015/17/B/ST6/01887

Słowa kluczowe:

przeszukiwanie grafów algorytmy optymalizacyjne złożoność obliczeniowa

Deskryptory:

  • 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 - Informatyka i technologie informacyjne: technologie i systemy informacyjne, informatyka, obliczenia naukowe, systemy inteligentne

Jednostka realizująca:

Politechnika Gdańska, Wydział Elektroniki, Telekomunikacji i Informatyki

woj. pomorskie

Inne projekty tej jednostki 

Kierownik projektu (z jednostki realizującej):

dr hab. Dariusz Dereniowski 

Liczba wykonawców projektu: 5

Konkurs: OPUS 9 - ogłoszony 2015-03-16

Przyznana kwota: 287 280 PLN

Rozpoczęcie projektu: 2016-01-27

Zakończenie projektu: 2019-12-26

Planowany czas trwania projektu: 47 miesięcy (z wniosku)

Status projektu: Projekt rozliczony

Opis Projektu

Pobierz opis projektu w formacie .pdf

Uwaga - opisy projektów zostały sporządzone przez samych autorów wniosków i w niezmienionej formie umieszczone w systemie.

Dane z raportu końcowego/rocznego

  • Publikacje w czasopismach (18)
  • Teksty w publikacjach pokonferencyjnych (12)
  1. Clearing Directed Subgraphs by Mobile Agents - Variations on Covering with Paths -
    Autorzy:
    Dariusz Dereniowski, Andrzej Lingas, Mia Persson, Dorota Urbańska, Paweł Żyliński
    Czasopismo:
    Journal of Computer and System Sciences (rok: 2019, tom: 102, strony: 57-68), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.jcss.2018.11.002 - link do publikacji
  2. Graphs with equal domination and covering numbers
    Autorzy:
    Andrzej Lingas, Mateusz Miotk, Jerzy Topp, Paweł Żyliński
    Czasopismo:
    Journal of Combinatorial Optimization (rok: 2020, tom: 39, strony: 55-71), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s10878-019-00454-6 - link do publikacji
  3. Total Dominating Sets in Maximal Outerplanar Graphs
    Autorzy:
    Magdalena Lemańska, Rita Zuazua, Paweł Żyliński
    Czasopismo:
    Graphs and Combinatorics (rok: 2017, tom: 33, strony: 991-998), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00373-017-1802-7 - link do publikacji
  4. Reconfiguring Minimum Dominating Sets in Trees
    Autorzy:
    Magdalena Lemańska, Paweł Żyliński
    Czasopismo:
    Journal of Graph Algorithms and Applications (rok: 2020, tom: 24, strony: 47-61), Wydawca: Brown University (wersja elektroniczna)
    Status:
    Opublikowana
    Doi:
    10.7155/jgaa.00517 - link do publikacji
  5. Vertex-edge domination in graphs
    Autorzy:
    Paweł Żyliński
    Czasopismo:
    Aequationes mathematicae (rok: 2019, tom: 93, strony: 735-742), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00010-018-0609-9 - link do publikacji
  6. Cops, a fast robber and defensive domination on interval graphs
    Autorzy:
    DariuszDereniowski, Tomáš Gavenčiak, Jan Kratochvíl
    Czasopismo:
    Theoretical Computer Science (rok: 2019, tom: 794, strony: 47-58), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.tcs.2018.09.031 - link do publikacji
  7. On Tradeoffs Between Width- and Fill-like Graph Parameters
    Autorzy:
    Dariusz Dereniowski, Adam Stański
    Czasopismo:
    Theory of Computing Systems (rok: 2019, tom: 63, strony: 450-465), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00224-019-09948-6 - link do publikacji
  8. A linear algorithm for connected domination in partial k-trees
    Autorzy:
    Radosław Ziemann
    Czasopismo:
    WSEAS Transaction on Mathematics (rok: 2019, tom: 18, strony: 237-240), Wydawca: World Scientific and Engineering Academy and Society
    Status:
    Opublikowana
    Doi:
    brak - link do publikacji
  9. How to keep an eye on small things
    Autorzy:
    Bengt J. Nilsson, Paweł Żyliński
    Czasopismo:
    International Journal of Computational Geometry & Applications (rok: 2020, tom: 30, strony: 97-120), Wydawca: World Scientific
    Status:
    Opublikowana
    Doi:
    10.1142/S0218195920500053 - link do publikacji
  10. Decontaminating Arbitrary Graphs by Mobile Agents: a Survey
    Autorzy:
    Dorota Osula
    Czasopismo:
    Utilitas Mathematica , Wydawca: Utilitas Mathematica Publishing Inc. Winnipeg, Manitoba, Canada
    Status:
    Przyjęta do publikacji
    Doi:
    brak - link do publikacji
  11. Building a Nest by an Automaton
    Autorzy:
    Jurek Czyzowicz, Dariusz Dereniowski, Andrzej Pelc
    Czasopismo:
    Algorithmica (rok: 2021, tom: 83, strony: 144-176), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00453-020-00752-0 - link do publikacji
  12. Convex dominating sets in maximal outerplanar graphs
    Autorzy:
    Magdalena Lemańska, Eduardo Rivera-Campo, Radosław Ziemann, Rita Zuazua, Paweł Żyliński
    Czasopismo:
    Discrete Applied Mathematics (rok: 2019, tom: 265, strony: 142-157), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.dam.2019.02.029 - link do publikacji
  13. Finding small-width connected path decompositions in polynomial time
    Autorzy:
    Dariusz Dereniowski, Dorota Osula, Paweł Rzążewski
    Czasopismo:
    Theoretical Computer Science (rok: 2019, tom: 794, strony: 85-100), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.tcs.2019.03.039 - link do publikacji
  14. On-line Search in Two-Dimensional Environment
    Autorzy:
    Dariusz Dereniowski, Dorota Osula
    Czasopismo:
    Theory of Computing Systems (rok: 2019, tom: 63, strony: 1819-1848), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00224-019-09948-6 - link do publikacji
  15. Searching by Heterogeneous Agents
    Autorzy:
    Dariusz Dereniowski, Łukasz Kuszner, Robert Ostrowski
    Czasopismo:
    Journal of Computer and System Sciences (rok: 2021, tom: 115, strony: 45312), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.jcss.2020.06.008 - link do publikacji
  16. Topology recognition and leader election in colored networks
    Autorzy:
    D.Dereniowski, A.Pelc
    Czasopismo:
    Theoretical Computer Science (rok: 2016, tom: 621, strony: 92-102), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.tcs.2016.01.037 - link do publikacji
  17. Vertex-edge domination in cubic graphs
    Autorzy:
    Radosław Ziemann, Paweł Żyliński
    Czasopismo:
    Discrete Mathematics (rok: 2020, tom: 343, strony: 112075), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.disc.2020.112075 - link do publikacji
  18. Energy Constrained Depth First Search
    Autorzy:
    Shantanu Das, Dariusz Dereniowski, Przemysław Uznański
    Czasopismo:
    Algorithmica , Wydawca: Springer
    Status:
    Złożona
    Doi:
    brak - link do publikacji
  1. Approximation Strategies for Generalized Binary Search in Weighted Trees
    Autorzy:
    Dariusz Dereniowski, Adrian Kosowski, Przemyslaw Uznański, Mengchuan Zou
    Konferencja:
    44th International Colloquium on Automata, Languages and Programming (rok: 2017, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 10-14 lipiec 2017
    Status:
    Opublikowana
  2. On-line Search in Two-Dimensional Environment
    Autorzy:
    Dariusz Dereniowski, Dorota Urbańska
    Konferencja:
    The 15th Workshop on Approximation and Online Algorithms (WAOA 2017) (rok: 2017, ), Wydawca: Springer
    Data:
    konferencja 7-8 wrzesień 2017
    Status:
    Opublikowana
  3. The Snow Team Problem (Clearing Directed Subgraphs by Mobile Agents)
    Autorzy:
    Dariusz Dereniowski, Andrzej Lingas, Mia Persson, Dorota Urbańska, Paweł Żyliński
    Konferencja:
    21st International Symposium on Fundamentals of Computation Theory, FCT 2017 (rok: 2017, ), Wydawca: Springer
    Data:
    konferencja 11-13 wrzesień 2017
    Status:
    Opublikowana
  4. A Framework for Searching in Graphs in the Presence of Errors
    Autorzy:
    Dariusz Dereniowski, Stefan Tiegel, Przemysław Uznański, Daniel Wolleb-Graf
    Konferencja:
    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:
    Opublikowana
  5. A note on guarding staircase polygons
    Autorzy:
    Matt Gibson, Erik Krohn, Bengt J. Nilsson, Matthew Rayford, Paweł Żyliński
    Konferencja:
    31st Canadian Conference on Computational Geometry (rok: 2019, ), Wydawca: University of Alberta (wersja elektroniczna)
    Data:
    konferencja 8-10 sierpień 2019
    Status:
    Opublikowana
  6. Brief Announcement: Energy Constrained Depth First Search
    Autorzy:
    Shantanu Das, Dariusz Dereniowski, Przemyslaw Uznanski
    Konferencja:
    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:
    Opublikowana
  7. Collaborative Delivery by Energy-Sharing Low-Power Mobile Robots
    Autorzy:
    Evangelos Bampas, Shantanu Das, Dariusz Dereniowski, Christina Karousatou
    Konferencja:
    The 13th International Symposium on Algorithms and Experiments for Wireless Networks (rok: 2017, ), Wydawca: Springer
    Data:
    konferencja 7-8 września 2017
    Status:
    Opublikowana
  8. Searching by Heterogeneous Agents
    Autorzy:
    Dariusz Dereniowski, Łukasz Kuszner, Robert Ostrowski
    Konferencja:
    11th International Conference on Algorithms and Complexity, CIAC 2019 (rok: 2019, ), Wydawca: Springer
    Data:
    konferencja 27-29 maj 2019
    Status:
    Opublikowana
  9. The lighthouse problem: Navigating by lighthouses in geometric domains
    Autorzy:
    Bengt J. Nilsson, Paweł Żyliński
    Konferencja:
    31st Canadian Conference on Computational Geometry (rok: 2019, ), Wydawca: University of Alberta (wersja elektroniczna)
    Data:
    konferencja 8-10 sierpień 2019
    Status:
    Opublikowana
  10. Building a Nest by an Automaton
    Autorzy:
    Jurek Czyzowicz, Dariusz Dereniowski, Andrzej Pelc
    Konferencja:
    27th Annual European Symposium on Algorithms, ESA 2019 (rok: 2019, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 9-11 wrzesień 2019
    Status:
    Opublikowana
  11. Generalized kernels of polygons under rotation: area and perimeter
    Autorzy:
    Alejandra Martínez-Moraian, David Orden, Leonidas Palios, Carlos Seara, Paweł Żyliński
    Konferencja:
    XVIII Spanish Meeting on Computational Geometry (rok: 2019, ), Wydawca: Universitat de Girona (wersja elektroniczna)
    Data:
    konferencja 1-3 lipiec 2019
    Status:
    Opublikowana
  12. Minimizing the Cost of Team Exploration
    Autorzy:
    Dorota Osula
    Konferencja:
    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:
    Opublikowana

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy