Search
prof. dr hab. inż. Marek Kubale
Publications
Filters
total: 125
Catalog Publications
Year 2015
-
Towards the boundary between easy and hard control problems in multicast Clos networks
PublicationIn this article we study 3-stage Clos networks with multicast calls in general and 2-cast calls, in particular. We investigate various sizes of input and output switches and discuss some routing problems involved in blocking states. To express our results in a formal way we introduce a model of hypergraph edge-coloring. A new class of bipartite hypergraphs corresponding to Clos networks is studied. We identify some polynomially...
Year 2014
-
Łagodne wprowadzenie do analizy algorytmów
PublicationKsiążka jest 11. wydaniem podręcznika akademickiego poświęconego podstawom algorytmiki. Składa się z trzech rozdziałów. Rozdział 1 daje podstawy formalne niezbędne przy analizie algorytmów pod kątem złożoności obliczeniowej. Rozdział 2 wprowadza w zagadnienia analizy algorytmów z różnych punktów widzenia.Rozdział 3 przedstawia podstawowe struktury danych.
-
Sprawiedliwe i półsprawiedliwe pokolorowania grafów kubicznych
PublicationW pracy rozpatrywane są sprawiedliwe i półsprawiedliwe pokolorowania grafów kubicznych. Pokazano, że w odróżnieniu od tego pierwszego, który jest łatwy, problem istnienia pokolorowań półsprawiedliwych jest NP-zupełny w szerokim zakresie parametrów grafów.
Year 2013
-
Equitable coloring of corona products of graphs
PublicationIn this paper we consider an equitable coloring of some corona products of graphs G and H in symbols, G o H). In particular, we show that deciding the colorability of G o H is NP-complete even if G is 4-regular and H is K_2. Next, we prove exact values or upper bounds on the equitable chromatic number of G o H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a path, a cycle or a complete graph.
Year 2012
-
Katedra Algorytmów i Modelowania Systemów
PublicationPrzedstawiono podstawowe informacje nt. Katedry Algorytmów i Modelowania Systemów Wydziału Elektroniki, Telekomunikacji i Informatyki PG. W szczególności przedstawiono rys historyczny, działalność dydaktyczną, badania podstawowe, nagrody i wyróżnienia oraz ofertę dla przemysłu.
-
Modele i metody kolorowania grafów. Część II
PublicationNiniejszy artykuł jest drugą częścią 2-odcinkowego cyklu przeglądowego na temat modeli i metod kolorowania grafów. Przedstawiono w nim najważniejsze, z punktu widzenia zastosowań, modele kolorowania grafów. W szczególności pokazano różne kryteria i ograniczenia modyfikujące kolorowanie klasyczne. Ponieważ kolorowanie we wszystkich tych odmianach i wariantach jest NP-trudne, podano oszacowania na liczbę chromatyczną (indeks chromatyczny)...
-
Product Graph Invariants with Applications in the Theory of Information
PublicationThere are a large number of graph invariants. In the paper, we consider some of them, e.g. the independence and chromatic numbers. It is well know that we cannot efficiently calculate these numbers for arbitrary graphs. In the paper we present relations between these invariants and concepts from the theory of information. Concepts such as source coding and transmission over a noisy channel with zero probability of error are modeled...
Year 2011
-
A Note on Shannon Capacity for Invariant and Evolving Channels
PublicationIn the paper we discuss the notion of Shannon capacity for invariant and evolving channels. We show how this notion is involved in information theory, graph theory and Ramsey theory.
-
Cztery algorytmy które wstrząsnęły światem. Część I: Wprowadzenie
PublicationArtykuł przeglądowy jest pierwszym fragmentem 3-częściowego szkicu popularnonaukowego poświęconego najważniejszym osiągnięciom w dziedzinie algorytmiki. Wprowadzono w nim w arkana złożoności obliczeniowej i sztuki programowania komputerów.
-
Cztery algorytmy które wstrząsnęły światem. Część II: Od czasu wykładniczego do wielomianowego
PublicationDrugi odcinek cyklu poświęcono problemowi programowania liniowego, który wywarł ogromny wpływ na życie milionów ludzi oraz badaniu liczb pierwszych, a więc problemowi ściśle związanemu z bezpieczeństwem naszych pieniędzy zdeponowanych w bankach.
-
Cztery algorytmy które wstrząsnęły światem. Część III: Sprzęt czy oprogramowanie
PublicationW trzecim odcinku cyklu poruszono problem przyjaznego rysowania grafów oraz zaprezentowano algorytmy dla szybkiego mnożenia macierzy, a więc problemu, który pojawia się w każdej nauce inżynieryjnej. Rozważania ogólne zamknięto ilustracją postępu, jaki dokonał się w zakresie sprzętu liczącego i oprogramowania.
-
Jak szybko gasić pożar, czyli przypadek szeregowania zadań czasowozależnych
Publicationartykuł poświęcony jest planowaniu pracy brygad strażackich walczących z pożarami lasu. model matematyczny, który tutaj zastosowano to szeregowanie zadań uwarunkowanych czasowo. przedyskutowano złożoność problemu w przypadku zastosowania dwóch kryteriów optymalizacji: długości harmonogramu i średniego czasu przepływu. pokazano, że w ogólności nie istnieją uszeregowania idealne, zapewniające minimalizację obu kryteriów jednocześnie
-
Million dollar algorithn?
PublicationArtykuł w sposób popularnonaukowy porusza następujące problemy:- 2300 lat algorytmiki- 7 problemów milenijnych- rodzaje problemów pod kątem złożoności obliczeniowej- planowanie optymalne- banki i grafy- czy P=NP?
-
Shannon Capacity and Ramsey Numbers
PublicationRamsey-type theorems are strongly related to some results from information theory. In this paper we present these relations.
Year 2010
-
Modele i metody kolorowania grafów. Część I
PublicationNiniejszy artykuł jest pierwszą częścią 2-odcinkowego cyklu przeglądowego na temat modeli i metod kolorowania grafów. Przedstawiono w nim najważniejsze, z punktu widzenia zastosowań, modele kolorowania grafów. W szczególności pokazano co można kolorować w grafie i jak to można kolorować. Ponieważ kolorowanie we wszystkich odmianach i wariantach jest NP-trudne, podajemy oszacowania na liczbę chromatyczną oraz potencjalne zastosowania...
-
Postępy algorytmiki i ich wpływ na rozwój informatyki w Polsce
PublicationPublikacja prezentuje najważniejsze polskie i światowe postępy algorytmiki i ich wpływ na rozwój informatyki w Polsce. w szczególności omówiono takie zagadnienia jak badanie pierwszości liczb, programowanie liniowe, płaskie rysowanie grafów i szybkie mnożenie macierzy.
-
Rearrangeability in multicast Clos networks is NP-complete
PublicationPrzestrajalność w polach Closa z połączeniami jeden do jeden jest problemem wielomianowym. W pracy pokazano, że w polach z połączeniami jeden do wiele problem ten jest NP zupełny.Three-stage elos networks are commutation networks with circuit switching. So far, graph theory has been very useful tool for solving issues related to these networks with unicast connections. This is so because if elos network is represented as a bipartite...
-
Scheduling jobs to contain a natural disaster: a model and complexity
Publicationthis paper is devoted to the problem of scheduling suppression units so that a natural disaster is dealt with as efficient as possible. the concept of deteriorating jobs is adopted, that is, the formal model of scheduling represents linearly increasing value loss as the disaster remains unsuppressed and increasing time for its suppression. more precisely, two different goals are considered: finding a suppression schedule of minimal...
Year 2009
-
A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints
PublicationWe address a generalization of the classical 1- and 2-processor unit execution time scheduling problem on dedicated machines. In our chromatic model of scheduling machines have non-simultaneous availability times and tasks have arbitrary release times and due dates. Also, the versatility of our approach makes it possible to generalize all known classical criteria of optimality. Under these stipulations we show that the problem...
-
A new optimal algorithm for a time-dependent scheduling problem
PublicationIn this article a single machine time-dependent scheduling problem with total completion time criterion is considered. There are n given jobs j_1, ..., j_n and the processing time pi of the i-th job is given by p_i = 1 + b_is_i, where si is the starting time of the i-th job, i = 1, ..., n. If all jobs have different and non-zero deterioration rates and bi > bj => bi >= (b_min+1)/(b_min) b_j + 1/b_min, where b_min = min{b_i}, then...
-
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
Publication -
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
PublicationW artykule rozważamy listowo-kosztowe kolorowanie wierzchołków i krawędzi grafu w modelu wierzchołkowym, krawędziowym, totalnym i pseudototalnym. Stosujemy programowanie dynamiczne w celu otrzymania algorytmów wielomianowych dla drzew. Następnie uogólniamy to podejście na dowolne grafy z ograniczonymi liczbami cyklomatycznymi i na ich multikolorowania.
-
Szeregowanie zadań wieloprocesorowych metodą kolorowania hiperkrawędzi
PublicationW artykule rozważamy problem szeregowania jednostkowych zadań wieloprocesorowych na procesorach dedykowanych z repetycją zadań i ograniczeniami dostępności. Prezentujemy zebrane wyniki złożoności dla różnych typów instancji powyższego problemu szeregowania z kryteriami długości harmonogramu, sumy czasów zakończenia zadań i kosztu całkowitego. Problem ten opisujemy modelem kolorowania krawędzi różnych klas hipergrafów.
Year 2008
-
Computer experiments with a parallel clonal selection algorithm for the graph coloring problem
PublicationArtificial immune systems (AIS) are algorithms that are based on the structure and mechanisms of the vertebrate immune system. Clonal selection is a process that allows lymphocytes to launch a quick response to known pathogens and to adapt to new, previously unencountered ones. This paper presents a parallel island model algorithm based on the clonal selection principles for solving the Graph Coloring Problem. The performance of...
-
program verification strategy and edge ranking of graphs
PublicationW artykule rozważamy model, w którym zakładamy, że dany jest zbiór asercji/testów dla pewnych bloków programu. Celem jest znalezienie optymalnej, tzn. wymagającej wykonania minimalnej liczby testów strategii wyszukiwania błędu w kodzie programu. Pomimo założenia w modelu, iż program posiada dokładnie jeden błąd, rozważania można uogólnić na testowanie kodu z dowolną liczbą błędów. Analizujemy teoretyczne własności tego modelu oraz...
Year 2007
-
Efficient list cost coloring of vertices and/or edges of some sparse graphs
PublicationRozważane jest kolorowanie wierzchołków i krawędzi grafów w modelach klasycznym, totalnym i pseudototalnym z uwzględnieniem dodatkowego ograniczenia w postaci list dostępnych kolorów. Proponujemy wielomianowy algorytm oparty na paradygmacie programowania dynamicznego dla grafów o strukturze drzewa. Wynik ten można uogólnić na grafy o liczbie cyklomatycznej ograniczonej z góry przez dowolnie wybraną stała.
-
Efficient List Cost Coloring of Vertices and∕or Edges of Some Sparse Graphs
Publication -
Model formalny dla problemu lokalizacji błędów w kodzie programu
PublicationIstnieje szereg sposobów badania poprawności programów komputerowych. W niniejszym referacie podejmujemy problem automatycznego testowania oprogramowania przy założeniu, iż dany jest zbiór testów (asercji) dla poszczególnych fragmentów kodu. Dla uproszczenia analizy zakładamy, że badany fragment kodu zawiera dokładnie jeden błąd, co nie zmniejsza ogólności rozważań. W artykule analizujemy praktyczne aspekty powyższego problemu...
Year 2006
-
Chromatic scheduling of 1- and 2-processor uet tasks on dedicated machines with availability constraints.
PublicationRozważono uogólnienie klasycznego szeregowania jednostkowych zadań jedno- i dwuprocesorowych na maszynach dedykowanych. Przyjęty model pozwala na naturalne wprowadzenie wszystkich klasycznych kryteriów optymalizacyjnych dla harmonogramów. Zaproponowano algorytmy wielomianowe dla systemów rzadkich.
-
Chromatic Scheduling of 1- and 2-Processor UET Tasks on Dedicated Machines with Availability Constraints
Publication -
Efficient parallel query processing by graph ranking
PublicationW artykule analizujemy przybliżony algorytm dla problemu szukania drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym, co znajduje zastosowanie w równoległym przetwarzaniu zapytań w relacyjnych bazach danych. Podajemy nowe oszacowanie uporządkowanego indeksu chromatycznego drzewa, które prowadzi do uzyskania lepszej funkcji dobroci wspomnianego algorytmu.
-
Equitable 4-coloring of cacti and edge-cacti in polynomial time
PublicationRozważono problem wyznaczania sprawiedliwej liczby chromatycznej kaktusów i drzew wielokątowych bez trójkątów i krawędzi wiszących. Podano wielomianowy algorytm wyznaczający pokolorowanie optymalne, oparty na paradygmacie programowania dynamicznego. Tym samym znaleziona została kolejna klasa grafów planarnych, dla której kolorowanie sprawiedliwe jawi się jako zagadnienie obliczeniowo łatwe.
-
Kolorowanie hipergrafów
PublicationHipergraf to struktura stanowiąca pewne uogólnienie grafu. Oprócz tradycyjnych krawędzi dwuelementowych dopuszcza ona także krawędzie, które zawierają inną, przeważnie większą liczbę wierzchołków. W tej pracy pokażemy kilka modeli kolorowania hipergrafów, takich jak kolorowanie krawędzi, kolorowanie wierzchołków i tzw. CD-kolorowanie, przedstawimy ich podstawowe własności oraz wskażemy zastosowania.
-
On some ramsey and turan-type numbers for paths and cycles
PublicationUdowodniono, że R(P_3,C_k,C_k)= R(C_k,C_k)= 2k - 1, dla nieparzystych k. Udowodniono, że R(P_4,P_4,C_k) = k + 2 oraz R(P_3,P_5,C_k) = k + 1 dla k > 2.
-
Parallel query processing and edge ranking of graphs
PublicationArtykuł poświęcony jest problemowi szukania drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym. Jednym z zastosowań jest poszukiwanie optymalnych harmonogramów w równoległym przetwarzaniu zapytań w relacyjnych bazach danych. Podajemy nowe oszacowanie funkcji dobroci przybliżonego algorytmu autorstwa Makino, Uno i Ibaraki wraz z rezultatami testów komputerowych przeprowadzonych dla grafów losowych.
-
Parallel tabu search for graph coloring problem
PublicationTabu search is a simple, yet powerful meta-heuristic based on local search that has been often used to solve combinatorial optimization problems like the graph coloring problem. This paper presents current taxonomy of patallel tabu search algorithms and compares three parallelization techniques applied to Tabucol, a sequential TS algorithm for graph coloring. The experimental results are based on graphs available from the DIMACS...
Year 2005
-
Chromatic scheduling in a cyclic open shop
PublicationPraca jest poświęcona złożoności obliczeniowej problemu cyklicznego szeregowania w systemie otwartym. Autorzy analizując wykazują, że problem jest NP-trudny dla 3 procesorów i konstruują algorytm dokładny dla przypadku dwóch procesorów.Ponadto analizowany jest zwarty wariant cyklicznego systemu otwartego. W tym przypadku autorzy pokazują, że już szeregowanie na dwóch procesorach prowadzi do problemu NP-trudnego.
-
Equitable vertex coloring of graphs
PublicationW pracy podajemy wartości sprawiedliwej liczby chromatycznej dla niektórych klas grafów. Podajemy również dwa algorytmy heurystyczne dla sprawiedliwego kolorowania grafów z suboptymalna liczba koloru.
-
Szeregowanie rozrzedzonych systemów zadań jednostkowych 1- i 2-procesorowych w oknach czasowych
PublicationSzeregowanie jednostkowych zadań 1- i 2-procesorowych z dodatkowym ograniczeniem w postaci zróżnicowanych okien czasowych, w których zadania te mogą być wykonywane zamodelowano przy pomocy listowego kolorowania i multikolorowania krawędzi grafów. Kryteria jakości harmonogramu: maksymalny koszt wykonania zadania w jednostce czasu oraz suma tychże kosztów po wszystkich zadaniach można przedstawić rozszerzając kolorowanie listowe...
-
The complexity of equitable vertex coloring graphs
PublicationW artykule podajemy wzory na sprawiedliwą liczbę chromatyczną niektórych produktów grafowych. Ponadto przedstawiamy dwa algorytmy wielomianowe dla sprawiedliwego kolorowania grafów suboptymalną liczba kolorów.
Year 2004
-
Cholesky factorization of matrices in parallel and ranking of graphs.
PublicationUporządkowane kolorowanie znajduje zastosowanie przy równoległej faktoryzacji macierzy metodą Cholesky'ego. Praca zawiera opis tego zastosowania. Podano także algorytmy optymalnego uporządkowanego kolorowania krawędzi pewnych klas grafów: grafów pełnych dwudzielnych oraz powstałych z pełnych dwudzielnych przez usunięcie O(log n) krawędzi.
-
Compact scheduling of zero–one time operations in multi-stage systems
Publication -
Compact scheduling of zero-one time operations in multi-stage systems.
PublicationRozważamy szeregowanie zwarte na maszynach dedykowanych z zero-jedynkowymi operacjami w modelu otwartym, przepływowym i mieszanym. Harmonogramy zostały zmodelowane przy pomocy pokolorowań krawędzi grafu konfliktów z pewnymi dodatkowymi ograniczeniami. Dowodzimy NP-trudności problemów w przypadku ogólnym oraz prezentujemy przegląd znanych wielomianowych algorytmów szeregujących dla systemów o specyficznej budowie.
-
Distributed largest-first algorithm for graph coloring.
PublicationW artykule zaprezentowano rozproszony, probabilistyczny algorytm kolorowania grafów. Kolorowanie uzyskane jest optymalne lub prawie optymalne dla takich klas grafów jak koła dwudzielne, gąsienice czy korony. Udowodniono, że algorytm ten działa w czasie O(D^2 log n) rund dla dowolnego grafu n wierzchołkowegoo stopniu maksymalnym D.
-
Harmonions Coloring of Graphs.
PublicationProblem kolorowania grafów jest motywowany radionawigacją lotniczą, kompresją obrazów i in. W rozdziale podano podstawowe fakty dotyczące tego modelu kolorowania, a wsród nich dolne i górne oszacowania na liczbę harmoniczną i algorytm o złożoności 0 (mm3) dający bardzo dobre pokolorowania przybliżone.
-
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 -
Wsadowe i cykliczne szeregowanie 1- i 2-procesorowych zadań jednostkowych na maszynach dedykowanych.
PublicationW pracy autorzy zajmują się modelem szeregowania zadań 1- i 2- procesorowych. Rozważane są przy tym dwa warianty: klasyczny określany jako wsadowy i cykliczny, który występuje w przypadku wielokrotnego powtarzania raz zaprojektowanego harmonogramu. Dla obu przypadków badane są własności teoretyczne i konstruowane algorytmy przybliżone.
Year 2003
-
Antypodalna radiowa liczba chromatyczna grafu.
PublicationOpisane zostały podstawowe zasady i właściwości antypodalnego kolorowania grafów. Zebrano publikowane w literaturze przedmiotu twierdzenia i uzupełniono wnioskami wynikającymi z własnych badań.
-
Metoda chromatyczna i jej zastosowania techniczne
PublicationArtykuł ma charakter przeglądowy. Przedstawiono w nim najważniejsze modele koloryzowania grafów i ich zastosowania w wybranych problemach technicznych. Ponieważ jest to wiodąca tematyka badawcza Katedry Podstaw Informatyki Wydziału ETI Politechniki Gdańskiej, praca służy również upowszechnianiu dorobku naukowego pracowników Katedry oraz osób z nią współpracujących w opisywanej dziedzinie.
seen 5879 times