Filters
total: 704
-
Catalog
Search results for: KOBALT
-
Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
Publication -
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
Publication -
Compact scheduling of zero–one time operations in multi-stage systems
Publication -
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...
-
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...
-
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.
-
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...
-
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.
-
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...
-
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...
-
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.
-
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.
-
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.
-
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.
-
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.
-
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ń.
-
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.
-
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...
-
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.
-
Programowanie dynamiczne w rozwiązywaniu problemów szeregowania zadań w systemach o acyklicznej strukturze
PublicationRozważono rozrzedzone systemy niepodzielnych zadań dwuprocesorowych o jednostkowych długościach operacji oraz systemy maszyn dedykowanych (open shop,flow shop, mixed shop) o operacjach zero-jedynkowych. Przedstawiono rodzinę wielomianowych algorytmów opartych na programowaniu dynamicznym, pozwalających na znalezienie optymalnego uszeregowania względem szerokiej rodziny funkcji kryterialnych. Stopień rozrzedzenia systemu zdefiniowano...
-
Algorytmy radiowego kolorowania grafów. XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych.
PublicationW pracy opisane są podstawowe zasady i właściwości radiowego kolorowania grafów. Podane są oszacowania radiowej liczby chromatycznej grafu w przypadku ogólnym, dla ścieżek i cykli oraz dokładne wartości radiowej liczby chromatycznej dla grafów pełnych k-dzielnych, kół i dwugwiazd. Zamieszczono także przykładowe wyniki porównania dobroci suboptymalnych, sekwencyjnych algorytmów radiokolorowania grafów.
-
Uporządkowane kolorowanie wierzchołków grafów
PublicationW pracy przedstawiamy stosunkowo nowy model kolorowania grafów, mianowicie kolorowanie uporządkowane. Po scharakteryzowaniu potencjalnych zastosowań tego modelu przedstawiamy liniowy algorytm kolorowania grafów w sposób przybliżony. Pokazujemy klasy grafów, które ten algorytm koloruje optymalnie i klasy grafów, dla których błąd pokolorowania może być dowolnie duży. Przedstawiamy również doświadczenia komputerowe zebrane w trakcie...
-
Better polynomial algorithms for scheduling unit-length jobs with bipartite incompatibility graphs on uniform machines
PublicationThe goal of this paper is to explore and to provide tools for the investigation of the problems of unit-length scheduling of incompatible jobs on uniform machines. We present two new algorithms that are a significant improvement over the known algorithms. The first one is Algorithm 2 which is 2-approximate for the problem Qm|p j = 1, G = bisubquartic|Cmax . The second one is Algorithm 3 which is 4-approximate for the problem Qm|p...
-
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...
-
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
-
Eqiuitable coloring of corona products of cubic graphs is harder than ordinary coloring
PublicationA graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G. In this paper the problem of determinig the equitable coloring number for coronas of cubic graphs is studied. Although the problem of ordinary coloring of coronas...
-
Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
PublicationIn the paper we consider the problems of equitable and semi-equitable coloring of vertices of cubic graphs. We show that in contrast to the equitable coloring, which is easy, the problem of semi-equitable coloring is NP- complete within a broad spectrum of graph parameters. This affects the complexity of batch scheduling of unit-length jobs with cubic incompatibility graph on three uniform processors to minimize...
-
A bound on the number of middle-stage crossbars in f-cast rearrangeable Clos networks
PublicationIn 2006 Chen and Hwang gave a necessary and sufficient condition under which a three-stage Clos network is rearrangeable for broadcast connections. Assuming that only crossbars of the first stage have no fan-out property, we give similar conditions for f-cast Clos networks, where f is an arbitrary but fixed invariant of the network. Such assumptions are valid for some practical switching systems, e.g. high-speed crossconnects....
-
A note on polynomial algorithm for cost coloring of bipartite graphs with Δ ≤ 4
PublicationIn the note we consider vertex coloring of a graph in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of coloring is the sum of costs incurred at each vertex. We show that the minimum cost coloring problem for n-vertex bipartite graph of degree ∆≤4 can be solved in O(n^2) time. This extends Jansen’s result [K.Jansen,The optimum cost chromatic partition problem, in:...
-
Potyczki algorytmiczne, czyli Alicja i Bogdan w nowych sytuacjach. 3. Alicja i Bogdan remontują mieszkanie.
PublicationPoniższe zagadki nawiązują z jednej strony do problemu kafelkowania płaszczyzny, który jest nierozstrzygalny, z drugiej do problemu rozkroju wstęgi, który jest NP-trudny. Jednakże przypadki szczególne, które tu rozważamy, nie są tak trudne i mogą być rozwiązane za pomocą algorytmów działających w czasie wielomianowym.
-
Potyczki algorytmiczne, czyli Alicja i Bogdan w nowych sytuacjach
PublicationW kolejnym odcinku serii z Alicją i Bogdanem najpierw ilustrujemy problem dominowania w grafach (kratowych): klasyczny i rzymski. Następnie ilustrujemy znany fakt, że zachłanność nie zawsze się opłaca. Pokażemy mianowicie, że algorytmy zachłanne nie gwarantują uzyskania rozwiązania optymalnego, nawet wówczas gdy problem da się rozwiązać w czasie wielomianowym.
-
Equitable colorings of some variation of corona products of cubic graphs
PublicationThe problem of determining the value of equitable chromatic number for multicoronas of cubic graphs is studied. We provide some polynomially solvable cases of cubical multicoronas and give simple linear time algorithms for equitable coloring of such graphs which use almost optimal number of colors in the remaining cases.
-
Preferencje przedstawicieli polskiego pokolenia dwudziestolatków w zakresie słodzonych sacharozą i dietetycznych napojów typu cola
PublicationCelem badania było zidentyfikowanie preferencji polskiego pokolenia dwudziestolatków w zakresie napojów typu cola. W badaniu udział wzięło 71 kobiet i 49 mężczyzn w wieku 20 – 21 lat. Badanie składało się z dwóch części: (1) ankiety dotyczącej zwyczajów związanych ze spożywaniem napojów typu cola oraz (2) konsumenckiej oceny sensorycznej napojów Coca – Coli oraz Coca – Coli light metodą parzystą za pomocą testu dwustronnego. Druga...
-
Special issue - ECCE-6
PublicationWskazano na nadmierną konsumpcję energii i substancji w porównaniu z rzeczywistym zapotrzebowaniem dla życia ludzkiego. Wskazano na skutki nadmiernie intensywnej eksploatacji surowców i zanieczyszczenie środowiska. Wskazano na wybitnie nierównomierny rozkład zużycia energii w świecie. Omówiono straty energii spowodowane emisją metanu z kopalń. Przedyskutowano możliwości i zasadnośc stosowania biopaliw. Omówiono rolę inżynierów...
-
Online pitch estimation using instantaneous complex frequency
PublicationW pracy opisano nowe wyniki dotyczące skuteczności algorytmu potokowego estymującego częstotliwość podstawową sygnału mowy. Algorytm wykorzystuje zespoloną pulsację chwilową dla klasyfikacji mowy na dźwięczną i bezdźwięczną oraz estymacji częstotliwości podstawowej dla każdej próbki sygnału. Skuteczność klasyfikacji oraz dokładność estymacji zostały ocenione eksperymentalnie z wykorzystaniem dwóch baz nagrań, zawierających wypowiedzi...
-
Wydatki na opiekę zdrowotna a wskaźniki zdrowotne na przykładzie wybranych państw OECD
PublicationW artykule przedstawiono korelację pomiędzy wydatkami na opiekę zdrowotną na osobę w $, wydatkami na administrację opieki zdrowotnej i ubezpieczeń w $ per capita a wskaźnikami zdrowotnymi. Z analizy danych wynika że istnieje silna korelacja ujemna pomiędzy wydatkami a wskaźnikiem zgonów i wskaźnikiem śmiertelności niemowląt oraz dodatnia korelacja pomiędzy wydatkami a przewidywana długością życia, silniejsza w wielu państwach dla...
-
Polscy inżynierowie elektrycy w 1936 r.
PublicationNa podstawie notek biograficznych ponad 1000 osób przedstawiono stan kadry inżynierskiej w zakresie elektrotechniki w 1936 r. Podano uczelnie, w których wykształcenie zdobywali polscy inżynierowie elektrycy. Omówiono liczbę osób z dyplomem inżyniera elektryka zamieszkujących poszczególne rejony przedwojennej Polski. Podano miejsca pracy w różnych dziedzinach działalności inżynierskiej. Omówiono zaangażowanie w działalność Związku...
-
Akademickie Mistrzostwa Polski w Piłce Ręcznej Kobiet
EventsAkademickie Mistrzostwa Polski w Piłce Ręcznej Kobiet - półfinał
-
Akademickie Mistrzostwa Polski w Piłce Ręcznej Kobiet
EventsAkademickie Mistrzostwa Polski w Piłce Ręcznej Kobiet - Finał
-
Mecz Energa Basket Ligi Kobiet w koszykówce
EventsEnerga Basket Ligi Kobiet w koszykówce: Sunreef Yachts Politechnika Gdańska – Arka Gdynia.
-
Akademickie Mistrzostwa Polski w Piłce Siatkowej Kobiet
EventsAkademickie Mistrzostwa Polski w Piłce Siatkowej Kobiet - Finał
-
Akademickie Mistrzostwa Polski w Koszykówce Kobiet -półfinał
EventsAkademickie Mistrzostwa Polski w Koszykówce Kobiet - półfinał A
-
Akademickie Mistrzostwa Polski w Piłce Siatkowej Kobiet
EventsAkademickie Mistrzostwa Polski w Piłce Siatkowej Kobiet - półfinał
-
Mecz Energa Basket Ligi Kobiet w koszykówce
EventsEnerga Basket Ligi Kobiet w koszykówce: DGT AZS Politechnika Gdańska – Energa Toruń
-
Mecz Energa Basket Ligi Kobiet w koszykówce
EventsEnerga Basket Ligi Kobiet w koszykówce: Sunreef Yachts Politechnika Gdańska – CCC Polkowice
-
Akademickie Mistrzostwa Polski w Futsalu Kobiet – półfinał
EventsPółfinał A Akademickich Mistrzostw Polski w Futsalu Kobiet, miejsce: Centrum Sportu Akademickiego PG. Więcej informacji: https://www.facebook.com/AMPfutsalkobiet.A.
-
Mecz Energa Basket Ligi Kobiet w koszykówce
EventsEnerga Basket Ligi Kobiet w koszykówce: Sunreef Yachts Politechnika Gdańska - Wisła Can-Pack Kraków
-
Akademickie Mistrzostwa Polski w Koszykówce Kobiet - finał
EventsAkademickie Mistrzostwa Polski w Koszykówce Kobiet - Finał
-
AMP w Siatkówce Plażowej Kobiet i Mężczyzn
EventsPółfinał A Akademickich Mistrzostw Polski w Siatkówce Plażowej Kobiet i Mężczyzn
-
Novel Polyurethanes as Antifouling Paint Matrices
PublicationThe new poly(ester-ether urethane)s (PEEUR) were prepared in two stage synthesis from formerly obtained oligo(alkylene ester-ether)diols (OAEE) and 4,4‘-diphenylmethane diisocyanate (MDI). PEEUR samples were subjected to crosslinking with styrene in the presence of radical polymerization initiators: methyl ethyl ketone peroxide (MEKPO) or cobalt 2-ethyl cyclohexanoate (EtHCo). Crosslinked PEEUR were characterized by their physicochemical...