Instytut Informatyki UG

TEMATYKA BADAWCZA

• Teoria grafów i jej zastosowania
• Kombinatoryka
• Algorytmy i struktury danych
• Złożoność obliczeniowa
• Optymalizacja dyskretna
• Geometria dyskretna i obliczeniowa
• Teoria współbieżności
• Sieci stochastyczne i ich niezawodność

SEMINARIUM ZAKŁADOWE

• Czwartek, godz. 14.15, sala 4.14 (budynek MFiI, nowe skrzydło)
• Kontakt w sprawie seminarium: dr Hanna Furmańczyk (Hanna.Furmanczyk@ug.edu.pl)
• Najbliższe referaty:

• Strona WWW: https://inf.ug.edu.pl/seminaria-algo

PRACE PRZYJĘTE do druku

• H. Furmańczyk, M. Kubale: Equitable colorings of l-corona products of cubic graphs. Ars Combinatoria.

SPIS PUBLIKACJI w roku 2022

• H. Furmańczyk, V. Mkrtchyan: Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs. Discrete Mathematics & Theoretical Computer Science 23(2), #7 (2022) [https://doi.org/10.46298/dmtcs.6860]
• M. Miotk, P. Żyliński: Spanning trees with disjoint dominating and 2-dominating sets. Discussiones Mathematicae Graph Theory 42(1), 299-308 (2022) [https://doi.org/10.7151/dmgt.2258]

SPIS PUBLIKACJI w roku 2021

• D. Dereniowski, Ł. Kuszner, R. Ostrowski: Searching by heterogeneous agents. Journal of Computer and System Sciences 115, 1-21 (2021) [https://doi.org/10.1016/j.jcss.2020.06.008]
• H. Furmańczyk, R. Zuazua: Equitable total coloring of corona of cubic graphs. Discussiones Mathematicae Graph Graph Theory 41(4), 1147-1163 (2021) [https://doi.org/10.7151/dmgt.2245]
• A. Martínez-Moraian, D. Orden, L. Palios, C. Seara, P. Żyliński: Optimizing generalized kernels of polygons. Journal of Global Optimization 80(4), 887-920 (2021) [https://doi.org/10.1007/s10898-021-01020-3]
• B.J. Nilsson, D. Orden, L. Palios, C. Seara, P. Żyliński: Illuminating the x-axis by α-floodlights. Proceedings of the 32nd International Symposium on Algorithms and Computation, LIPIcs 212, 11.1-11.12 (2021) [https://doi.org/10.1007/978-3-030-58150-3_25]

SPIS PUBLIKACJI w roku 2020

• M. Dettlaff, M. Lemańska, J. Topp, R. Ziemann, P. Żyliński: Certified domination. AKCE International Journal of Graphs and Combinatorics 17(1), 86-97 (2020) [https://doi.org/10.1016/j.akcej.2018.09.004]
• E. Drgas-Burchardt, H. Furmańczyk, E. Sidorowicz: Equitable d-degenerate choosability. Proceedings of the 31st International Workshop on Combinatorial Algorithms, Lecture Notes in Computer Science 12126, 251-263 (2020) [https://doi.org/10.1007/978-3-030-48966-3_19]
• E. Drgas-Burchardt, H. Furmańczyk, E. Sidorowicz: Equitable improper choosability of graphs. Theoretical Computer Science 844, 34-45 (2020) [https://doi.org/10.1016/j.tcs.2020.08.001].
• J.Dybizbański, T. Dzido, R. Zakrzewska: On-line Ramsey numbers for paths and short cycles. Discrete Applied Mathematics 282, 265-270 (2020) [https://doi.org/10.1016/j.dam.2020.03.004]
• H. Furmańczyk, V. Kowsalya, J. Vernold Vivin: On star coloring of splitting graphs. Ars Combinatoria 153, 33-39 (2020).
• M. Lemańska, P. Żyliński: Reconfiguring minimum dominating sets in trees. Journal of Graph Algorithms and Applications 24(1), 47-61 (2020) [https://doi.org/10.7155/jgaa.00517]
• A. Lingas, M. Miotk, J. Topp, P. Żyliński: Graphs with equal domination and covering numbers. Journal of Combinatorial Optimization 39, 55-71 (2020) [https://doi.org/10.1007/s10878-019-00454-6]
• M. Miotk, J. Topp, P. Żyliński: Disjoint dominating and 2-dominating sets in graphs. Discrete Optimization 35, Article 100553 (2020) [https://doi.org/10.1016/j.disopt.2019.100553]
• B.J. Nilsson, D. Orden, L. Palios, C. Seara, P. Żyliński: Shortest watchman tours in simple polygons under rotated monotone visibility. Proceedings of the 26th International Computing and Combinatorics Conference, Lecture Notes in Computer Science 12273, 311-323 (2020) [https://doi.org/10.1007/978-3-030-58150-3_25]
• B.J. Nilsson, P. Żyliński: How to keep an eye on small things. International Journal of Computational Geometry & Applications 30(2), 97-120 (2020) [https://dx.doi.org/10.1142/S0218195920500053]
• R. Ramanathan, M. Rosicka, K. Horodecki, S. Pironio, M. Horodecki, P.Horodecki: Gadget structures in proofs of the Kochen-Specker theorem. Quantum 4, 308 (2020) [https://doi.org/10.22331/q-2020-08-14-308]
• R. Ziemann, P. Żyliński: Vertex-edge domination in cubic graphs. Discrete Mathematics 343(11), Article 112075 (2020) [https://doi.org/10.1016/j.disc.2020.112075]

SPIS PUBLIKACJI w roku 2019

• E.C. Akrida, J. Czyzowicz, L. Gąsieniec, Ł. Kuszner, P. G. Spirakis: Temporal flows in temporal networks. Journal of Computer and System Sciences 103, 46-60 (2019) [https://doi.org/10.1016/j.jcss.2019.02.003]
• J. Cyman, M.A. Henning, J. Topp: On accurate domination in graphs. Discussiones Mathematicae Graph Theory 39, 615-627 (2019) [https://doi.org/10.7151/dmgt.2182]
• D. Dereniowski, Ł. Kuszner, R. Ostrowski: Searching by heterogeneous agents. CIAC'19, Lecture Notes in Computer Science 11485, 199-211 (2019) [https://doi.org/10.1007/978-3-030-17402-6_17]
• D. Dereniowski, A. Lingas, M. Persson, D. Urbańska, P. Żyliński: Clearing directed subgraphs by mobile agents (Variations on covering with paths). Special Issue of FCT'17, Journal of Computer and System Sciences 102, 57-68 (2019) [https://doi.org/10.1016/j.jcss.2018.11.002]
• M. Dettlaff, M. Lemańska, M. Miotk, J. Topp, R. Ziemann, P. Żyliński: Graphs with equal domination and certified domination numbers. Opuscula Mathematica 39(6), 815-827 (2019) [https://doi.org/10.7494/OpMath.2019.39.6.815]
• M. Dettlaff, J. Raczek, J. Topp: Domination subdivision and domination multisubdivision numbers of graphs. Discussiones Mathematicae Graph Theory 39(4), 829-839 (2019) [https://doi.org/10.7151/dmgt.2103]
• L. Gąsieniec, E. Pacheco, A. Farrugia, Ł. Kuszner: Deterministic rendezvous with different maps. Journal of Computer and System Sciences 106, 49-59 (2019) [https://doi.org/10.1016/j.jcss.2019.06.001]
• H. Furmańczyk, P. Obszarski: Equitable coloring of hypergraphs. Discrete Applied Mathematics 261, 186-192 (2019) [https://doi.org/10.1016/j.dam.2019.01.016]
• M. Gibson, E. Krohn, B.J. Nilsson, M. Rayford, P. Żyliński: A note on guarding staircase polygons. Proceedings of the 31st Canadian Conference on Computational Geometry, 101-105 (2019) [https://sites.ualberta.ca/~cccg2019/cccg2019_proceedings.pdf]
• F. Khoeini, T. Dzido: On some three color Ramsey numbers for paths, cycles, stripes and stars, Graphs and Combinatorics 35(2) (2019) 559-567 [https://doi.org/10.1007/s00373-019-02013-6]
• A. Kostulak: Model procesowego zarządzania bezpieczeństwem systemów informacyjnych szkół wyższych, Wydawnictwo Uniwersytetu Gdańskiego, ISBN 978-83-7865-903-7 (2019)
• M. Lemańska, E. Rivera-Campo, R. Ziemann, R. Zuazua, P. Żyliński: Convex dominating sets in maximal outerplanar graphs. Discrete Applied Mathematics 265, 142-157 (2019) [https://doi.org/10.1016/j.dam.2019.02.029]
• A. Martínez-Moraian, D. Orden, L. Palios, C. Seara, P. Żyliński: Generalized kernels of polygons under rotation: area and perimeter. Proc. of the XVIII Spanish Meeting on Computational Geometry, 1-4 (2019) [https://imae.udg.edu/egc2019/doc/BookAbstractsEGC2019.pdf]
• M. Miotk, J. Topp, P. Żyliński: Bipartization of Graphs. Graphs and Combinatorics 35(5), 1169-1177 (2019). [https://doi.org/10.1007/s00373-019-02068-5]
• B.J. Nilsson, P. Żyliński: The Lighthouse Problem – Navigating by lighthouses in geometric domains. Proceedings of the 31st Canadian Conference on Computational Geometry, 71-77 (2019) [someerrorCCCG2019.pdf].

  Note from the Authors. Unfortunately, at the time of presentation of these results, the authors encountered a counterexample to Lemma 4, thus invalidating the results claimed up to and including Theorem 7.

• P. Żyliński: Vertex-edge domination in graphs. Aequationes Mathematicae 93(4), 735-742 (2019) [https://doi.org/10.1007/s00010-018-0609-9]

SPIS PUBLIKACJI w roku 2018

• M. Dettlaff, M. Lemańska, J. Topp, P. Żyliński: Coronas and domination subdivision number of a graph. Bulletin of the Malaysian Mathematical Sciences Society 41(4), 1717-1724 (2018) [https://doi.org/10.1007/s40840-016-0417-0]
• E. Drgas-Burchardt, J. Dybizbański, H. Furmańczyk: E. Sidorowicz, Equitable list vertex colourability and arboricity of grids. Filomat 32(18), 6353-6374 (2018) [https://journal.pmf.ni.ac.rs/filomat/index.php/filomat/article/view/8510]
• T. Dzido, A. Jastrzębski: Turán numbers for odd wheels. Discrete Mathematics 341(4), 1150-1154 (2018) [https://doi.org/10.1016/j.disc.2017.10.003]
• H. Furmańczyk, A. Koliński: Wydajny algorytm dla r-sprawiedliwego kolorowania grafów. Automatyzacja procesów dyskretnych. Teoria i zastosowania, Wydawnictwo Politechniki Śląskiej (2018) [https://kkapd.pl/new/index.php/pliki-do-pobrania/category/5-tom-i-2018]
• H. Furmańczyk, M. Kubale: Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines. Discrete Applied Mathematics 234, 210-217 (2018) [https://doi.org/10.1016/j.dam.2016.01.036]
• H. Furmańczyk, M. Kubale: Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs. Discrete Applied Mathematics 237, 116-122 (2018) [https://doi.org/10.1016/j.dam.2017.12.002]
• H. Furmańczyk, J. Vernold Vivin, N. Mohanapriya: r-dynamic chromatic number of some line graphs. Indian Journal of Pure and Applied Mathematics 49(4), 591-600 (2018) [https://doi.org/10.1007/s13226-018-0288-1]
• M. Miotk, J. Topp: Hangable graphs. International Journal of Advances in Mathematics 4, 44-50 (2018) [https://adv-math.com/hangable-graphs/]
• D. Orden, L. Palios, C. Seara, P. Żyliński: Generalized kernels of polygons under rotation. Proc. of the 30th EuroCG, 74:1-6 (2018) [https://conference.imp.fu-berlin.de/eurocg18/download/paper_74.pdf]

SPIS PUBLIKACJI w roku 2017

• D. Dereniowski, A. Lingas, M. Persson, D. Urbańska, P. Żyliński: The Snow Team Problem (Clearing Directed Subgraphs by Mobile Agents) /Extended abstract/. FCT'17, Lecture Notes in Computer Science 10472, 190-203 (2017) [https://doi.org/10.1007/978-3-662-55751-8_16]
• H. Furmańczyk, M. Kubale, V. V. Mkrtchyan: Equitable coloring of corona multiproducts of graphs. Discussiones Mathematicae Graph Theory 37(4), 1079-1094 (2017) [https://doi.org/10.7151/dmgt.1992]
• H. Furmańczyk, M. Kubale: Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines. Bulletin of the Polish Academy of Sciences: Technical Sciences 65(1), 29-34 (2017) [https://doi.org/10.1515/bpasts-2017-0004]
• M. Krzywkowski, J. Topp: On interval and indifference graphs, Mathematical Reports 19, 1-5 (2017) [https://imar.ro/journals/Mathematical_Reports/php/2017/Mrc17_1.php]
• M. Lemańska, R. Zuazua, P. Żyliński: Total dominating sets in maximal outerplanar graphs. Graphs and Combinatorics 33(4), 991-998 (2017) [https://doi.org/10.1007/s00373-017-1802-7]
• K. Myslitski, J. Rak, Ł. Kuszner: Towards fast calculation of communication paths for resilient routing. Networks 70(4) /Special Issue on Design of Resilient Communication Networks/, 308-326 (2017) [http://doi.org/10.1002/net.21789]
• M. Pawłowska, R. Filipów, G. Krzykowski, A. Stanisławska-Sachadyn, L. Morzuch, J. Kulczycka, A. Balcerska, J. Limon: Coincidence of PTPN22 c.1858CC and FCRL3 -169CC genotypes as a biomarker of preserved residual β-cell function in children with type 1 diabetes. Pediatric Diabetes 18(8), 696-705 (2017) [https://doi.org/10.1111/pedi.12429]

SPIS PUBLIKACJI w roku 2016

• J. Dybizbański, T. Dzido, S. Radziszowski: On some values of three-color Ramsey numbers for paths. Discrete Applied Mathematics 204, 133-141 (2016) [https://doi.org/10.1016/j.dam.2015.11.002]
• H. Furmańczyk, A. Jastrzębski, M. Kubale: Equitable coloring of graphs. Recent theoretical results and new practical algorithms. Archives of Control Sciences 26(3), 281-295 (2016) [https://doi.org/10.1515/acsc-2016-0016]
• H. Furmańczyk, M. Kubale: Equitable coloring of corona products of cubic graphs is harder than ordinary coloring. Ars Mathematica Contemporanea 10(2), 333-347 (2016) [https://doi.org/10.26493/1855-3974.687.99b]
• H. Furmańczyk, M. Kubale, S. Radziszowski: On bipartization of cubic graphs by removal of an independent set. Discrete Applied Mathematics 209, 115-121 (2016) [https://doi.org/10.1016/j.dam.2015.10.036]
• M. Krzywkowski, J. Topp: On homogeneously representable interval graphs. National Academy Science Letters 39, 39-41 (2016) [https://doi.org/10.1007/s40009-015-0397-x]