Search
dr hab. inż. Michał Małafiejski
Publications
Filters
total: 61
Catalog Publications
Year 2022
-
Global defensive secure structures
PublicationLet S ⊂ V (G) for a given simple non-empty graph G. We define for any nonempty subset X of S the predicate SECG,S(X) = true iff |NG[X]∩S| ≥ |NG[X]\S|. Let H be a non-empty family of graphs such that for each vertex v ∈ V (G) there is a subgraph H of G containing v and isomorphic to a member of H. We introduce the concept of H-alliance extending the concept of global defensive secure structures. By an H-alliance in a graph G we...
Year 2021
-
Interval Edge Coloring of Bipartite Graphs with Small Vertex Degrees
PublicationAn edge coloring of a graph G is called interval edge coloring if for each v ∈ V(G) the set of colors on edges incident to v forms an interval of integers. A graph G is interval colorable if there is an interval coloring of G. For an interval colorable graph G, by the interval chromatic index of G, denoted by χ'_i(G), we mean the smallest number k such that G is interval colorable with k colors. A bipartite graph G is called (α,β)-biregular...
-
Total chromatic sum for trees
PublicationThe total chromatic sum of a graph is the minimum sum of colors (natural numbers) taken over all proper colorings of vertices and edges of a graph. We provide infinite families of trees for which the minimum number of colors to achieve the total chromatic sum is equal to the total chromatic number. We construct infinite families of trees for which these numbers are not equal, disproving the conjecture from 2012.
Year 2020
-
Tight bounds on global edge and complete alliances in trees
PublicationIn the talk the authors present some tight upper bounds on global edge alliance number and global complete alliance number of trees. Moreover, we present our NP-completeness results from [8] for global edge alliances and global complete alliances on subcubic bipartite graphs without pendant vertices. We discuss also polynomial time exact algorithms for finding the minimum global edge alliance on trees [7] and complete alliance...
Year 2019
-
Global edge alliances in graphs
PublicationIn the paper we introduce and study a new problem of finding a minimum global edge alliance in a graph which is related to the global defensive alliance (Haynes et al., 2013; Hedetniemi, 2004) and the global defensive set (Lewoń et al., 2016). We proved the NP-completeness of the global edge alliance problem for subcubic graphs and we constructed polynomial time algorithms for trees. We found the exact values of the size of the...
Year 2018
-
On incidence coloring of coloring of complete multipartite and semicubic bipartite graphs
PublicationIn the paper, we show that the incidence chromatic number of a complete k-partite graph is at most ∆+2 (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to ∆+1 if and only if the smallest part has only one vertex.
Year 2017
-
Interval incidence coloring of subcubic graphs
PublicationIn this paper we study the problem of interval incidence coloring of subcubic graphs. In [14] the authors proved that the interval incidence 4-coloring problem is polynomially solvable and the interval incidence 5-coloring problem is N P-complete, and they asked if χii(G) ≤ 2∆(G) holds for an arbitrary graph G. In this paper, we prove that an interval incidence 6-coloring always exists for any subcubic graph G with ∆(G) = 3.
-
No-Wait & No-Idle Open Shop Minimum Makespan Scheduling with Bioperational Jobs
PublicationIn the open shop scheduling with bioperational jobs each job consists of two unit operations with a delay between the end of the first operation and the beginning of the second one. No-wait requirement enforces that the delay between operations is equal to 0. No-idle means that there is no idle time on any machine. We model this problem by the interval incidentor (1, 1)-coloring (IIR(1, 1)-coloring) of a graph with the minimum...
-
Restricted open shop scheduling
PublicationIn the real applications the open shop scheduling models often require some additional constraints and adequate models. We concern the restrictions in the open shop scheduling related to an instance of the problem and to a feasible solution. Precisely, we require that each jobs consists of the bounded number of operations and each machine has a bounded load (i.e., the total number of operations executed on this machine in a schedule)....
-
Równowaga strategiczna dla zbiorów defensywnych w drzewach
PublicationW pracy rozważany jest problem defensywnej równowagi strategicznej dla zbiorów defensywnych w drzewach (spójnych grafach acyklicznych), który polega na znalezieniu dwóch rozłącznych globalnych zbiorów defensywnych. Zagadnienie to znajduje zastosowanie w modelo- waniu problemów komunikacyjnych w sieciach. Dla danego grafu G podzbiór jego wierzchołków S jest zbiorem defensywnym, jeśli dla każdego wierzchołka v należącego do S spełniony...
-
Szeregowanie zadań dwuprocesorowych w systemach otwartych
PublicationW pracy rozważany jest problem szeregowania zadań dwuoperacyjnych w systemie otwartym (open-shop), z kryterium minimalizacji długości harmonogramu oraz sumy czasów zakończenia wszystkich zadań. Zakładając jednostkowe czasy wykonywania operacji można stosować efektywne metody chromatyczne rozwiązywania problemu, poprzez sprowadzenie go do modelu grafowego oraz zastosowanie w nim wybranego modelu kolorowania, które pozwala uzyskać...
Year 2016
-
Global defensive sets in graphs
PublicationIn the paper we study a new problem of finding a minimum global defensive set in a graph which is a generalization of the global alliance problem. For a given graph G and a subset S of a vertex set of G, we define for every subset X of S the predicate SEC ( X ) = true if and only if | N [ X ] ∩ S | ≥ | N [ X ] \ S | holds, where N [ X ] is a closed neighbourhood of X in graph G. A set S is a defensive alliance if and only if for...
-
Strategic balance in graphs
PublicationFor a given graph G, a nonempty subset S contained in V ( G ) is an alliance iff for each vertex v ∈ S there are at least as many vertices from the closed neighbourhood of v in S as in V ( G ) − S. An alliance is global if it is also a dominating set of G. The alliance partition number of G was defined in Hedetniemi et al. (2004) to be the maximum number of sets in a partition of V ( G ) such that each set is an alliance. Similarly,...
Year 2015
-
Graph security testing
PublicationSet S ⊂ V is called secure set iff ∀ X ⊂ S | N [ X ] ∩ S | ≥ | N ( X ) \ S | [3]. That means that every subset of a secure set has at least as many friends (neighbour vertices in S) as enemies (neighbour vertices outside S) and will be defended in case of attack. Problem of determining if given set is secure is co −NP -complete, there is no efficient algorithm solving it [3]. Property testers are algorithms that distinguish inputs...
-
Interval incidence graph coloring
PublicationIn this paper we introduce a concept of interval incidence coloring of graphs and survey its general properties including lower and upper bounds on the number of colors. Our main focus is to determine the exact value of the interval incidence coloring number χii for selected classes of graphs, i.e. paths, cycles, stars, wheels, fans, necklaces, complete graphs and complete k-partite graphs. We also study the complexity of the...
Year 2014
-
Algorithms for testing security in graphs
PublicationIn this paper we propose new algorithmic methods giving with the high probability the correct answer to the decision problem of security in graphs. For a given graph G and a subset S of a vertex set of G we have to decide whether S is secure, i.e. every subset X of S fulfils the condition: |N[X] \cap S| >= |N[X] \ S|, where N[X] is a closed neighbourhood of X in graph G. We constructed a polynomial time property pseudotester based...
-
Interval incidence coloring of bipartite graphs
PublicationIn this paper we study the problem of interval incidence coloring of bipartite graphs. We show the upper bound for interval incidence coloring number (χii) for bipartite graphs χii≤2Δ, and we prove that χii=2Δ holds for regular bipartite graphs. We solve this problem for subcubic bipartite graphs, i.e. we fully characterize the subcubic graphs that admit 4, 5 or 6 coloring, and we construct a linear time exact algorithm for subcubic...
Year 2010
-
Interval wavelength assignment in all-optical star networks
PublicationArtykuł omawia zwarte końcówkowe kolorowanie grafów, które jest matematycznym modelem dla problemu przydziału częstotliwości w sieciach optycznych. W artykule przedstawiono wielomianowe algorytmy wyznaczania zwartej końcówkowej liczby chromatycznej dla pełnych grafów k-dzielnych, drzew i podkubicznych grafów dwudzielnych.
Year 2009
-
On efficient coloring of chordless graphs
PublicationArtykuł omawia zagadnienie optymalnego, wielomianowego rozpoznawania i kolorowania grafów bezcięciwowych. Zawiera dowód tego, że takie grafy są zawsze 4-kolorowalne oraz opis wielomianowego algorytmu, który koloruje je minimalną możliwą liczbą kolorów.
-
The complexity of the L(p,q)-labeling problem for bipartite planar graphs of small degree
PublicationW pracy pokazano, że problem L(p,q)-kolorowania przy użyciu ''t'' kolorów jest NP-zupełny nawet w wersji ograniczonej do grafów planarnych dwudzielnych małego stopnia, nawet dla stosunkowo niewielkich wartości ''t''. Jako wniosek z uzyskanych wyników stwierdzono, że problem L(2,1)-kolorowania grafów planarnych przy użyciu 4 kolorów jest NP-zupełny, a także że problem L(p,q)-kolorowania grafów o maksymalnym stopniu 4 jest NP-zupełny...
Year 2008
-
Application of an online judge & contester system in academic tuition
PublicationPraca zawiera opis systemu typu ''Online judge & contester'' o nazwie SPOJ, wykorzystywanego do zdalnej nauki programowania. Został on pomyślnie wdrożony w nauczaniu informatyki na Politechnice Gdańskiej. Omówiono zasadę działania i mechanizmy bezpieczeństwa systemu SPOJ. Przedstawiono wnioski z doświadczeń przy stosowaniu tego typu systemów w nauczaniu na etapie studiów 1. i 2. stopnia w ciągu ostatnich czterech lat.
-
Tighter bounds on the size of a maximum P3-matching in a cubic graph
PublicationW pracy pokazano, że największe P3-skojarzenie dla dowolnego grafu o n>16 wierzchołkach składa się z przynajmniej 117n/152 wierzchołków.
Year 2007
-
A polynomial algorithm for some preemptive multiprocessor task scheduling problems.
Publication.
-
Application of an online judge & contester system in academic tuition
PublicationPraca zawiera opis systemu typu ''Online judge & contester'' o nazwie SPOJ, wykorzystywanego do zdalnej nauki programowania. Został on pomyślnie wdrożony w nauczaniu informatyki na Politechnice Gdańskiej. Omówiono zasadę działania i mechanizmy bezpieczeństwa systemu SPOJ. Przedstawiono wnioski z doświadczeń przy stosowaniu tego typu systemów w nauczaniu na etapie studiów 1. i 2. stopnia w ciągu ostatnich czterech lat.
-
Cooperative mobile guards in grids
PublicationPraca dotyczy problemu strzeżenia dwuwymiarowych krat ortogonalnych, przy założeniu, że obszar widoczności strażnika obejmuje jedną ulicę oraz wszystkie ulice ją przecinające. Rozważano wariant straży słabo współpracujących, w którym dodatkowo każdy strażnik musi widzieć przynajmniej jednego innego strażnika. Podano dowód NP-trudności problemu optymalizacyjnego w przypadku ogólnym, algorytm dokładny o złożoności O(n log n) dla...
-
Kolorowanie końcówkowe multidrzew
PublicationW pracy przedstawiono nowy model kolorowania grafów, mianowicie kolorowanie końcówkowe. Naszkicowano związki łączące ten model z klasycznymi modelami kolorowania oraz przedstawiono wielomianowy algorytm optymalnie końcówkowo kolorujący multidrzewa.
-
Packing [1,Delta]-factors in graphs of small degree
PublicationRozważano problem znalezienia w grafie zadanej liczby k krawędziowo rozłącznych [1,Delta]-faktorów, gdzie Delta oznacza stopień grafu. Problem ten można rozwiązać w czasie liniowym dla k=2, jest on jednak NP-trudny dla każdego k>=3. Pokazano, że wariant minimalizacjny problemu dla k=2 jest NP-trudny dla grafów planarnych podkubicznych, jednak w ogólności istnieje algorytm (42 Delta - 30) / (35 Delta - 21) - aproksymacyjny.
-
Zwarte końcówkowe kolorowanie grafów
PublicationPraca dotyczy jednego z nowych modeli kolorowania grafów, tzw. zwartego końcówkowego kolorowania. Praca zawiera definicję modelu, informacje o jego zastosowaniach, dolne i górne oszacowania na liczbę kolorów oraz wartości dokładne zwartego końcówkowego indeksu dla wybranych klas grafów: ścieżek, cykil, gwiazd, kół, grafów pełnych i innych.
Year 2006
-
An approximation algorithm for maximum P3-packing in subcubic graphs
PublicationW pracy podano algorytm 4/3-przyliżony dla trudnego obliczeniowo problemu umieszczania wierzchołkowo rozłącznych dwukrawędziowych ścieżek w grafach o stopniu maksymalnym 3 i stopniu minimalnym 2. Poprawiono tym samym wcześniejsze wyniki dla grafów kubicznych (A. Kelmans, D. Mubayi, Journal of Graph Theory 45, 2004).
-
An efficient algorithm for mobile guarded guards in simple grids
PublicationW pracy rozważono problem strzeżenia ortogonalnych krat dwuwymiarowych przez mobilne straże strzeżone. Podano algorytmy wielomianowe m.in. dla przypadku krat prostych i dla przypadku krat bez przeszkód w kierunku poziomym (pionowym).
-
Fault tolerant guarding of grids
PublicationW pracy rozważano problem strzeżenia krat dwuwymiarowych przez dwa niezależne zespoły straży. Wykazano, że zagadnienie minimalizacyjne jest NP-trudne i zaproponowano dla niego wielomianowy algorytm 6/5-przybliżony.
-
Identyfikacja terenu za pomocą autonomicznego robota
PublicationW pracy rozważane jest zagadnienie identyfikacji nieznanego terenuprzy pomocy autonomicznego robota o ograniczonym zasięguwidzialności. Przyjęty model matematyczny zakłada, że teren mapostać ograniczonej dwuwymiarowej mapy podzielonej na identycznekwadratowe obszary (pola) przylegające do siebie bokami. Zadaniemautonomicznego robota, którego zasięg widzialności ogranicza siedo pól przylegających do miejsca, w którym się znajduje,...
-
Parallel processing subsystems with redundancy in a distributed environment
PublicationW pracy rozważano problem podziału systemu rozproszonego na spójne podsystemy złożone z przynajmniej trzech jednostek, pozwalające na detekcję i skorygowanie pojedynczych błędów. Wykazano, że problem maksymalizacji liczby takich jednostek jest NP-trudny nawet dla dwuspójnych kubicznych topologii sieci. Podano też nowe algorytmy przybliżone.
Year 2005
-
Analiza systemu zabezpieczeń dla internetowego portalu typu Online Judge
PublicationPrzedmiotem rozważań jest powszechnie dostępny portal internetowy pozwalający na organizację zawodów programistycznych. System taki, określany popularnie jako online judge lub online contester, udostępnia użytkownikom do rozwiązania zestaw zadań o charakterze algorytmicznym. Reguły konkursów oraz treści i zasady oceny poszczególnych zadań ustalane są przez uprzywilejowanych użytkowników zarządzających swoimi konkursami poprzez...
-
Bezpieczeństwo w systemie internetowym Sphere Online Judge
PublicationPrzedmiotem rozważań jest powszechnie dostępny portal internetowy udostępniający do rozwiązania wielu problemów o charakterze algorytmicznym. Użytkownicy za pośrednictwem przeglądarki internetowej nadsyłają programy, będące rozwiązaniami zadań, które są następnie kompilowane, uruchamiane i oceniane. Ze względu na charakter systemu, jego bezpieczeństwo jest niezmiernie ważne.
-
Internetowy system dydaktyczny typu online judge
PublicationOmówiony w pracy system typu Online Judge został wykorzystany na przedmiotach związanych z algorytmiką i optymalizacją dyskretną na Wydziale ETI Politechniki Gdańskiej. Najważniejsze funkcje systemu, z punktu widzenia dydaktyki, pozwalają na wykorzystanie go do automatycznej oceny rozwiązań problemów algorytmicznych, jako repozytorium dokumentów (sprawozdań) oraz jako platformę do zarządzania przedmiotem z możliwością kontroli...
-
On bounded load routings for modeling k-regular connection topologies
PublicationW pracy analizowane są problemy modelowania k-regularnych topologii sieci komputerowych z punktu widzenia routingu typu point-to-point. Zaprezentowane są algorytmy oraz przeprowadzona jest analiza złożoności obliczeniowej.
-
Packing three-vertex paths in a subcubic graph
PublicationW pracy rozważany jest problem pakowania scieżek P3 w grafach podkubicznych, pokazano oszacowania dolne na ilość ścieżek w zależności od stopnia spójności grafu oraz minimalnego stopnia.
-
Weakly cooperative guards in grids
PublicationW pracy autorzy zajmują się rozmieszczaniem strażników mobilnych w kratach ortogonalnych, podali wzór na minimalną liczbę strażników w kracie oraz przeanalizowali złożoność obliczeniową problemu.
-
Zintegrowany system do automatycznej oceny rozwiązań oraz prowadzenia zajęć laboratoryjno-projektowych : Sphere Online Judge
PublicationW pracy zaprezentowano system Sphere Online Judge (SPOJ), z powodzeniem wdrożony na przedmiotach związanych z algorytmiką i optymalizacją dyskretną na Wydziale Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej. Podstawowe funkcje systemu, z punktu widzenia dydaktyki, pozwalają na wykorzystanie go do automatycznej oceny rozwiązań problemów algorytmicznych, jako repozytorium dokumentów (sprawozdań) oraz platformę...
Year 2004
-
Koncepcja środowiska umożliwiającego symulację działań obiektów militarnych.
PublicationPraca zawiera opis najbardziej popularnych platform symulacji walki robotów militarnych. Przeanalizowano ich główne wady i ograniczenia programowe oraz nieadekwatność odtworzenia rzeczywistych warunków i przebiegu walki. Na tym tle przedstawiono oryginalną koncepcję oraz założenia projektowe środowiska symulacji działań autonomicznych obiektów (robotów) militarnych. Proponowana platforma ma umożliwić:- porównanie jakości taktyk...
-
Sum coloring of bipartite graphs with bounded degree.
PublicationArtykuł poświęcony jest złożoności obliczeniowej zagadnienia sumacyjnego kolorowania grafów dwudzielnych o ograniczonym stopniu. Zawiera dowód tego, że sumacyjne kolorowanie grafów dwudzielnych stopnia mniejszego równego 5 jest NP-zupełne oraz opis wielomianowego algorytmu, który optymalnie sumacyjnie koloruje grafy dwudzielne podkubiczne.
-
Sum Coloring of Bipartite Graphs with Bounded Degree
Publication -
Sum Coloring of Graphs.
PublicationRozdział jest poświęcony sumacyjnemu kolorowaniu grafów. Przedstawiono jego podstawowe własności oraz zastosowania praktyczne.
-
Weakly cooperative mobile guards in grids.
PublicationProblem straży w kratach stanowi przypadek problemu minimalnego pokrycia spójnego podzbioru płaszczyzny przez pewne szczególne podzbiory. W modelu tym przyjmuje się, że strażnik porusza się wzdłuż odcinka kraty i widzi wszystkie przecinające się z nim (prostopadłe) odcinki. W rozważanym modelu współpracy zakłada się, że każdy strażnik musi być widziany przez przynajmniej jednego innego strażnika. W pracy pokazano dowód NP-zupełności...
Year 2003
-
A polynomial algorithm for finding T-span of generalized cacti.
PublicationW pracy opisano wielomianowy algorytm wyznaczający optymalne T-pokolorowania dla uogólnionych kaktusów.
-
Algorytm przybliżony dla cyrkularnego kolorowania krawędzi grafów
PublicationW artykule autorzy proponują algorytm przybliżony dla cylkularnego kolorowania krawędzi grafu. Przedstawione są oszacowania na złożoność obliczeniową tego algorytmu, a także wyniki testów na grafach o małej liczbie wierzchołków jak i na grafach losowych.
-
An experimental study of distributed algorithms for graph coloring.
PublicationW pracy podano algorytm rozproszonego kolorowania grafówi porównano ze znanym wcześniej algorytmem.
-
The complexity of the T-coloring problem for graphs with small degree.
PublicationW pracy ustalono złożoność obliczeniową problemu optymalnego kolorowania grafów o ustalonym stopniu.
-
Uszeregowania zadań wieloprocesorowych minimalizuje średni czas przepływu
PublicationW artykule rozważane są problemy efektywnego wyznaczania uszeregowań wieloprocesorowych dla zadań jednostkowych na dedykowanych procesorach równoległych, które minimalizują średni czas przepływu.
seen 2823 times