Wyszukiwarka
Filtry
wszystkich: 3553
wybranych: 3330
-
Katalog
- Publikacje 3330 wyników po odfiltrowaniu
- Czasopisma 6 wyników po odfiltrowaniu
- Konferencje 1 wyników po odfiltrowaniu
- Osoby 37 wyników po odfiltrowaniu
- Wynalazki 2 wyników po odfiltrowaniu
- Projekty 1 wyników po odfiltrowaniu
- Laboratoria 1 wyników po odfiltrowaniu
- Zespoły Badawcze 1 wyników po odfiltrowaniu
- Kursy Online 65 wyników po odfiltrowaniu
- Wydarzenia 6 wyników po odfiltrowaniu
- Dane Badawcze 103 wyników po odfiltrowaniu
Filtry wybranego katalogu
wyświetlamy 1000 najlepszych wyników Pomoc
Wyniki wyszukiwania dla: PROBLEM KOLOROWANIA MAP
-
A 27/26-approximation algorithm for the chromatic sum coloring of bipartitegraphs
PublikacjaWe consider the CHROMATIC SUM PROBLEM on bipartite graphs which appears to be much harder than the classical CHROMATIC NUMBER PROBLEM. We prove that the CHROMATIC SUM PROBLEM is NP-complete on planar bipartite graphs with Delta less than or equal to 5, but polynomial on bipartite graphs with Delta less than or equal to 3, for which we construct an O(n(2))-time algorithm. Hence, we tighten the borderline of intractability for this...
-
The maximum edge-disjoint paths problem in complete graphs
PublikacjaRozważono problem ścieżek krawędziowo rozłącznych w grafach pełnych. Zaproponowano wielomianowe algorytmy: 3.75-przybliżony (off-line) oraz 6.47-przybliżony (on-line), poprawiając tym samym wyniki wcześniej znane z literatury [P. Carmi, T. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs, in: Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science, in: LNCS, vol. 2880, 2003, pp. 143-155]. Ponadto...
-
Zastosowanie Systemu Informacji Geograficznej (GIS) w identyfikacji potencjalnych klastrów
PublikacjaPolityka klastrowania znajduje się w strategicznych dokumentach rozwoju gospodarczego Polski i nastawiona jest na promowanie współpracy regionalnej ponadregionalnej. Budowa klastra na szczeblu regionalnym wymaga jednak w pierwszym etapie jego identyfikacji a w kolejnym selekcji potencjalnych uczestników. Dotychczas stosowane jakościowe i ilościowe metody identyfikacji klastrów, nie są do takich zadań przystosowane lub ich stopień...
-
Szeregowanie zadań wieloprocesorowych metodą kolorowania hiperkrawędzi
PublikacjaW 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.
-
Parallel tabu search for graph coloring problem
PublikacjaTabu 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...
-
Narzędzia treningu twórczości jako pomoc w kształceniu projektantów
PublikacjaKreatywność rozwijać. Na tym założeniu opiera się międzynarodowy program edukacyjny Odyssey of the Mind (Odyseja Umysłu). W programie zespoły młodych osób pracują metodą projektową, wykorzystując różnorodne techniki treningu twórczości, nad rozwiązaniem abstrakcyjnego problemu rozbieżnego. Część absolwentów programu wybiera kierunki kreatywne jako naturalną kontynuację procesu edukacji. Elementy treningu twórczości można wykorzystać...
-
Degree of entaglement as a physically ill-posted problem: The case of entaglement with vacuum
PublikacjaAnalizujemy przypadek fotonu w superpozycji różnych modów i zadajemy pytanie o stopień ich splątania z próżnią. Problem okazuje się być źle postawiony, gdyż nie wiemy którą reprezentację algebry CCR wybrać dla kwantowania pola. Gdy dokonamy wyboru jednoznacznie możemy rozwiązać zagadnienie splątania. Tak więc trudność nie leży w matematyce lecz w fizyce problemu.
-
Algorytm samostabilizujący dla problemu kolorowania krawędzi grafu.
PublikacjaReferat ten poświęcony jest kolorowaniu grafów w modelu rozproszonym.Podano samostabilizujący się algorytm kolorowania krawędzi grafu. Jest to prawdopodobnie pierwszy algorytm krawędziowego kolorowania grafów w tym modelu. Rozważania teoretyczne zostały poparte eksperymentami komputerowymi.
-
Przybliżone algorytmy uporządkowanego kolorowania krawędzi multidrzew.
PublikacjaNiniejszy referat omawia zagadnienie uporządkowanego kolorowania krawędzi multidrzew. Opisano w nim dwa przybliżone algorytmy dla tego problemu, zbadano ich własności teoretyczne oraz przedstawiono wyniki testów komputerowych, jakim zostały poddane.
-
O pewnym zastosowaniu uporządkowanego kolorowania grafów
PublikacjaPraca opisuje związki pomiędzy problemami uporządkowanego kolorowania wierzchołków grafów oraz szukania drzewa eliminacji o minimalnej wysokości dla danego grafu. Stąd wynika przydatność tytułowego problemu przy równoległej faktoryzacji macierzy metodą Cholsky´ego.
-
Modele i metody kolorowania grafów. Część I
PublikacjaNiniejszy 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...
-
Modele i metody kolorowania grafów. Część II
PublikacjaNiniejszy 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)...
-
Sekwencyjne algorytmy antypodalnego kolorowania radiowego grafów.
PublikacjaPraca zawiera charakterystykę suboptymalnych algorytmów antypodalnego kolorowania grafów, stanowiących adaptację algorytmów sekwencyjnych S, SL, LF stosowanych przy klasycznym kolorowaniu grafów. Dla tych algorytmów wskazano grafy dość trudne i trudne do pokolorowania (HC i SHC). Porównano ich funkcję dobroci i rozpiętości uzyskiwanych pokolorowań dla grafów o różnej gęstości krawędziowej.
-
Samostabilizujące się algorytmy wierzchołkowego kolorowania grafów.
PublikacjaArtykuł jest poświęcony kolorowaniu grafów w modelu rozproszonym. Podano schemat konstruowania samostabilizujących się algorytmów wierzchołkowego kolorowania grafów z możliwością nadawania wierzchołkom priorytetów. W oparciu o tę technikę skonstruowano samostabilizujący się algorytm LF który został szczegółowo opisany. Przeprowadzono również testy komputerowe porównując algorytm LF ze znanymi wcześniej algorytmami samostabilizującymi.
-
Zachłanne algorytmy kolorowania grafów w modelu rozproszonym
PublikacjaW artykule porównano cztery rozproszone algorytmy kolorowania grafów. Zaprezentowano wyniki eksperymentów komputerowych, w których badano liczbę rund i kolorów uzyskanych dla grafów losowych.
-
Constructing a map of an anonymous graph: applications of universal sequences
PublikacjaWe study the problem of mapping an unknown environmentrepresented as an unlabelled undirected graph. A robot (or automaton)starting at a single vertex of the graph G has to traverse the graph and return to its starting point building a map of the graph in the process. We are interested in the cost of achieving this task (whenever possible) in terms of the number of edge traversal made by the robot. Another optimization criteria...
-
Algorytm przybliżony dla cyrkularnego kolorowania krawędzi grafów
PublikacjaW 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.
-
Wybrane własności problemu routingu oraz kolorowania ścieżek w grafie.
PublikacjaReferat dotyczy zagadnienia ścieżkowego kolorowania grafu, które stanowi naturalny model dla problemu routingu i przydziału częstotliwości w czysto optycznej sieci światłowodowej. Opisano podstawowe zasady i właściwości ścieżkowego kolorowania grafów. Zaprezentowano wybrane twierdzenia, oparte w dużej mierze na wynikach badań własnych. Omówiono złożoność obliczeniową problemu routingu chromatycznego i kolorowania ścieżek zarówno...
-
Firing map of an almost periodic input function
PublikacjaIn mathematical biology and the theory of electric networks the firing map of an integrate-and-fire system is a notion of importance. In order to prove useful properties of this map authors of previous papers assumed that the stimulus function f of the system ẋ = f(t,x) is continuous and usually periodic in the time variable. In this work we show that the required properties of the firing map for the simplified model ẋ = f(t) still...
-
Metaheurystyki dla problemu routingu oraz kolorowania ścieżek w grafie.
PublikacjaReferat dotyczy zagadnienia ścieżkowego kolorowania grafu, które stanowi naturalny model dla problemu routingu i przydziału częstotliwości w czysto optycznej sieci światłowodowej. Zagadnienie optymalizacyjne dla zadanego zbioru zgłoszeń polega na minimalizacji największej użytej wartości koloru ścieżki (tzw. liczby chromatycznej zbioru zgłoszeń). Opisano podstawowe zasady i właściwości ścieżkowego kolorowania grafów. Porównano...
-
Samostabilizujący się algorytm kolorowania grafów dwudzielnych i kaktusów
PublikacjaW pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm kolorowania grafów oparty na konstrukcji drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm z gwarantowaną wielomianową liczbą ruchów, który dokładnie koloruje grafy dwudzielne.
-
Matching trajectory of a person to a map in inertial navigation system
PublikacjaPaper describes the method of matching, to a map, trajectories of a person walking indoors, obtained from inertial navigation module. General principle of matching algorithm based on particle filtering is presented. Method of detecting particle collisions is described as well. The last chapter provides test results of map matching related to a true trajectory.
-
Szeregowanie zadań sprzężonych metodą kolorowania grafów
PublikacjaRozważono problem szeregowania zadań sprzężonych na pojedynczym procesorze w obecności ograniczeń kolejnościowych. Zidentyfikowano przypadki wielomianowe dla tego zagadnienia NP-trudnego.
-
Parallel scheduling by graph ranking
PublikacjaNr dokum.: 73017Praca dotyczy jednego z nieklasycznych modeli kolorowania grafów - uporządkowanego kolorowania. Celem było uzyskanie wyników, które mogo być wykorzystane w praktycznych zastosowaniach tego modelu, do których należą: równoległe przetwarzanie zapytań w relacyjnych bazach danych, równoległa faktoryzacja macierzy metodą Choleskiego, równoległa asemblacja produktu z jego części składowych. W pracy wskazano uogólnienia...
-
Eksperymenty z zastosowanie algorytmów genetycznych do problemu kolorowania grafów
PublikacjaNiniejsza praca przedstawia wykorzystanie algorytmów genetycznych (AG) do problemu kolorowania wierzchołków grafu (GCP). Przeprowadzono szereg symulacji mających na celu porównanie skuteczności operatorów krzyżownia, mutacji i selekcji oraz sposobu generacji i parametrów populacji. Uzyskane wyniki pokazały znaczną przewagę operatorów korzystających z wiedzy o problemie nad operatorami losowymi. Dla wybranej konfiguracji algorytmu...
-
Bifurcation in von Karman problem for rectangular, thin, elastic plate resting on elastic foundation of Winkler type
PublikacjaPraca poświęcona jest utracie stateczności prostokątnej, cienkiej płyty sprężystej spoczywającej na podłożu liniowo sprężystym typu Winklera. Płyta jest ściskana równomiernie rozłożonymi obciążeniami na dwóch równoległych brzegach. Wyznaczono obciążenia krytyczne, formy utraty stateczności płyty oraz początkowe zachowanie pokrytyczne. Analizę prowadzono za pomocą analizy funkcjonalnej przy zachowaniu precyzyjnego matematycznego...
-
Algorytmy radiowego kolorowania grafów. XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych.
PublikacjaW 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.
-
An absorbing set for the Chialvo map
PublikacjaThe classical Chialvo model, introduced in 1995, is one of the most important models that describe single neuron dynamics. In order to conduct effective numerical analysis of this model, it is necessary to obtain a rigorous estimate for the maximal bounded invariant set. We discuss this problem, and we correct and improve the results obtained by Courbage and Nekorkin (2010). In particular, we provide an explicit formula for an...
-
Periodic and chaotic dynamics in a map‐based neuron model
PublikacjaMap-based neuron models are an important tool in modeling neural dynamics and sometimes can be considered as an alternative to usually computationally costlier models based on continuous or hybrid dynamical systems. However, due to their discrete nature, rigorous mathematical analysis might be challenging. We study a discrete model of neuronal dynamics introduced by Chialvo in 1995. In particular, we show that its reduced one-dimensional...
-
On the complexity of distributed greedy coloring
PublikacjaW pracy rozważono problem kolorowania grafów przy dodatkowym założeniu, że kolor żadnego wierzchołka nie może zostać zmniejszony bez zmiany kolorów przynajmniej jednego z jego sąsiadów. Przeprowadzone rozważania dotyczyły złożoności obiczeniowej problemu w modelu Liniala obliczeń rozproszonych. Podano ograniczenia dolne i górne złożoności problemu oraz zestawiono problem z innymi pokrewnymi zagadnieniami grafowymi.
-
Zastosowanie superkomputera do tworzenia dynamicznych map hałasu
PublikacjaW artykule przedstawiono koncepcję i implementację Modelu Dynamicznego Prognozowania Hałasu przeznaczonego do tworzenia map hałasu. Omówiony został cel wykonania powstałej aplikacji. Zawarto krótki opis użytego sprzętu. Omówiono poszczególne elementy Modelu Dynamicznego Prognozowania Hałasu oraz zastosowane metody. Przedstawiono zagadnienia związane z implementacją algorytmów na klastrze komputerowym. Zaprezentowano również rezultaty...
-
The complexity of the L(p,q)-labeling problem for bipartite planar graphs of small degree
PublikacjaW 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...
-
Spike patterns and chaos in a map-based neuron model
PublikacjaThe work studies the well-known map-based model of neuronal dynamics introduced in 2007 by Courbage, Nekorkin and Vdovin, important due to various medical applications. We also review and extend some of the existing results concerning β-transformations and (expanding) Lorenz mappings. Then we apply them for deducing important properties of spike-trains generated by the CNV model and explain their implications for neuron behaviour....
-
Statistical properties of a modified standard map in quantum and classical regimes
PublikacjaWe present a model—a modified standard map. This model has interesting properties that allow quantum–classical correspondences to be studied. For some range of parameters in the classical phase space of this model, there exist large accelerator modes. We can create a family of maps that have large accelerator modes.
-
TWORZENIE MAP SIECI KOMPUTEROWYCH Z WYKORZYSTANIEM PROTOKOŁÓW TYPU LLDP
PublikacjaDla administratorów systemów sieciowych niezwykle istot-nym jest posiadanie narzędzia tworzącego dynamicznie mapę sieci do celów zarządzania, diagnostyki, zapobiegania awariom i włamaniom. Artykuł prezentuje protokoły wspierające tworzenie map sieci a także własne badania nad usprawnieniem istniejących algorytmów. Proponowane rozwiązania to: budowa map z użyciem protokołu LLDP i SNMP, odkrywanie wąskich gardeł w sieciach dzięki...
-
Analysis of dynamics of a map-based neuron model via Lorenz maps
PublikacjaModeling nerve cells can facilitate formulating hypotheses about their real behavior and improve understanding of their functioning. In this paper, we study a discrete neuron model introduced by Courbage et al. [Chaos 17, 043109 (2007)], where the originally piecewise linear function defining voltage dynamics is replaced by a cubic polynomial, with an additional parameter responsible for varying the slope. Showing that on a large...
-
The complexity of equitable vertex coloring graphs
PublikacjaW 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.
-
Using Disparity Map for Moving Object Position Estimation in Pan Tilt Camera Images
PublikacjaIn this paper we present the algorithm for rapid moving object position estimation in an images acquired from pan tilt camera. Detection of a moving object in a image acquired from a moving camera might be quite challenging. Standard methods that relay on analyzing two consecutive frames are not applicable due to the changing background. To overtake this problem we decided to evaluate the possibility of calculating a disparity...
-
Creating and application of maps of concepts for dl ontologies
PublikacjaW poprzednich pracach wprowadzono metodę reprezentacji wiedzy, zwaną Kartografią Wiedzy. Metoda ta pozwala na zapisanie, w formie tzw. map konceptów, zależności pomiędzy konceptami wyróżnionymi w terminologii, a następnie stopniowe (wraz ze wzrostem naszej wiedzy) przypisywanie indywidualnym obiektom tych konceptów. Efektywność budowy map konceptów jest kluczowym czynnikiem wpływającym na możliwość użycia metody. Niniejsza praca...
-
Zastosowanie algorytmu MSA (Multiple Similar Areas) do wyznaczania map głębi w wielowidokowych systemach widzenia komputerowego
PublikacjaArtykuł podejmuje temat pozyskiwania map głębi (ang. depth map) na podstawie zdjęć z wielu kamer w wyniku widzenia stereoskopowego. Mapa głębi zawierająca odległości od obiektów będących w zasięgu widzenia kamer pozyskana może zostać na podstawie zdjęć z co najmniej dwóch kamer pełniących funkcję kamery stereoskopowej. W mapach głębi pozyskanych w ten sposób występują jednak błędy. Artykuł dotyczy metod redukcji błędów dzięki zwiększeniu...
-
Wyznaczanie map hałasu z wykorzystaniem chmury obliczeniowej
PublikacjaW referacie przedstawiono gridow usług obliczeniow Mapy Hałasu. Algorytm predykcji hałasu i model ródła powstał w ramach bada Katedry Systemów Multimedialnych, Politechniki Gdaskiej. Aplikacja webowa umoliwia wykonanie map akustycznych, w szczególnoci hałasu drogowego bez uycia dodatkowego oprogramowania komercyjnego. W pracy przedstawiono zagadnienia z tematyki modelowania hałasu i propagacji dwiku w przestrzeniach miejskich....
-
Analysing the Residential Market Using Self-Organizing Map
PublikacjaAlthough the residential property market has strong connections with various sectors, such as construction, logistics, and investment, it works through different dynamics than other markets; thus, it can be analysed from various perspectives. Researchers and investors are mostly interested in price trends, the impact of external factors on residential property prices, and price prediction. When analysing price trends, it is beneficial...
-
Easy and hard instances of arc ranking in directed graphs
PublikacjaArtykuł dotyczy uporządkowanego kolorowania łuków grafów skierowanych. Problem polega na takim przyporządkowaniu liczb łukom digrafu, aby każda skierowana ścieżka łącząca dwa łuki o tej samej liczbie (kolorze) zawierała łuk o kolorze wyższym. Praca podaje liniowy optymalny algorytm dla pewnego szczególnego przypadku, oraz zawiera dowód, iż problem ten jest obliczeniowo trudny dla 3-dzielnych acyklicznych digrafów i stałej liczby...
-
The complexity of the T-coloring problem for graphs with small degree.
PublikacjaW pracy ustalono złożoność obliczeniową problemu optymalnego kolorowania grafów o ustalonym stopniu.
-
Zastosowanie algorytmów rojowych do kolorowania grafów
PublikacjaPrzedstawiamy sposób adaptacji heurystycznej metody przeszukiwania PSO (ang. Particle Swarm Optimization) do znajdowania suboptymalnych pokolorowań wierzchołkowych grafów prostych. Prezentujemy sposób przeprowadzenia eksperymentów obliczeniowych oraz ich wyniki.
-
Szeregowanie zadań metodami kolorowania grafów.Monografie 37.
PublikacjaNiniejsza praca poświęcona jest wykorzystaniu teorii chromatycznej grafów w szeregowaniu. Koncepcja ta polega na przedstawieniu zbioru zadań w postaci krawędzi tzw. grafu konfliktów.
-
A note on mixed tree coloring
PublikacjaZaproponowano liniowy algorytm dla problemu kolorowania mieszanego w drzewach, uzyskując tym samym poprawę w stosunku do algorytmu o złożoności O(n^2) podanego w pracy [P. Hansen, J. Kuplinsky, D. de Werra, Mixed graph colorings, Math. Methods Oper. Res. 45 (1997) 145-160].
-
Performance of Noise Map Service Working in Cloud Computing Environment
PublikacjaIn the paper a noise map service designated for the user interested in environmental noise subject is presented. It is based on cloud computing. Noise prediction algorithm and source model, developed for creating acoustic maps, are working in cloud computing environment. In the study issues related to noise modeling of sound propagation in urban spaces are discussed with a special focus on road noise. Examples of results obtained...
-
Self-stabilizing algorithms for graph coloring with improved performance guarantees
PublikacjaW pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm kolorowania grafów oparty na konstrukcji drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm z gwarantowaną wielomianową liczbą ruchów, który dokładnie koloruje grafy dwudzielne.
-
Hat problem on a graph
PublikacjaThe topic of our paper is the hat problem. In that problem, each of n people is randomly fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color looking at the hat colors of the other people. The team wins if at least one person guesses his hat color correctly and no one guesses his hat color wrong, otherwise the team loses. The aim is to maximize the probability of win. In this version every...