Publikacje
Filtry
wszystkich: 119
Katalog Publikacji
-
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...
-
Game with a Purpose for Mappings Verification
PublikacjaMappings verification is a laborious task. The paper presents a Game with a Purpose based system for verification of automatically generated mappings. General description of idea standing behind the games with the purpose is given. Description of TGame system, a 2D platform mobile game with verification process included in the gameplay, is provided. Additional mechanisms for anti-cheating, increasing player’s motivation and gathering...
-
Optimization of Data Assignment for Parallel Processing in a Hybrid Heterogeneous Environment Using Integer Linear Programming
PublikacjaIn the paper we investigate a practical approach to application of integer linear programming for optimization of data assignment to compute units in a multi-level heterogeneous environment with various compute devices, including CPUs, GPUs and Intel Xeon Phis. The model considers an application that processes a large number of data chunks in parallel on various compute units and takes into account computations, communication including...
-
Interval incidence coloring of bipartite graphs
PublikacjaIn 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...
-
Crowdsourcing-Based Evaluation of Automatic References Between WordNet and Wikipedia
PublikacjaThe paper presents an approach to build references (also called mappings) between WordNet and Wikipedia. We propose four algorithms used for automatic construction of the references. Then, based on an aggregation algorithm, we produce an initial set of mappings that has been evaluated in a cooperative way. For that purpose, we implement a system for the distribution of evaluation tasks, that have been solved by the user community....
-
Improvement of Imperfect String Matching Based on Asymetric n-Grams
PublikacjaTypical approaches to string comparing treats them as either different or identical without taking into account the possibility of misspelling of the word. In this article we present an approach we used for improvement of imperfect string matching that allows one to reconstruct potential string distortions. The proposed method increases the quality of imperfect string matching, allowing the lookup of misspelled words without significant...
-
Assessing Word Difficulty for Quiz-Like Game
PublikacjaMappings verification is a laborious task. Our research aims at providing a framework for manual verification of mappings using crowdsourcing approach. For this purpose we plan on implementing a quiz like game. For this purpose the mappings have to be evaluated in terms of difficulty to better present texts in respect of game levels. In this paper we present an algorithm for assessing word difficulty. Three approaches...
-
Static and dynamic approach of social roles identification using PISNA and subgraphs matching
PublikacjaIdentyfikacja ról w sieci społecznej jest jednym z podstawowych zagadnień analiza takich sieci. W artykule przedstawiamy nowe podejście do tego zagadnienia. Pokazujemy w jaki sposób można dokonać identyfikacji ról poprzez tworzenie specjalnych struktur grafowych tzw. grafów wzorcowych. Przy definiowaniu tychże grafów wspieramy się metodą PISNA. Proponujemy statyczne i dynamiczne podejście do identyfikacji ról. Pokazujemy, w jaki...
-
Towards facts extraction from text in Polish language
PublikacjaNatural Language Processing (NLP) finds many usages in different fields of endeavor. Many tools exists allowing analysis of English language. For Polish language the situation is different as the language itself is more complicated. In this paper we show differences between NLP of Polish and English language. Existing solutions are presented and TEAMS software for facts extraction is described. The paper shows also evaluation of...
-
Primary role identification in dynamic social networks
PublikacjaIdentyfikacja ról w sieci społecznej jest jednym z podstawowych zagadnień analizy takich sieci. W artykule przedstawiamy nowe podejście do tego zagadnienia. Pokazujemy w jaki sposób można dokonać identyfikacji ról poprzez wykorzystanie zaproponowanego modelu zachowań aktorów. Model taki tworzą podgrafy wzorcowe oraz diagramy stanów okreslające sekwencje aktywności w zachowaniu aktorów. Na bazie wyznaczonych modeli zachowań oraz...
-
On incidence coloring of coloring of complete multipartite and semicubic bipartite graphs
PublikacjaIn 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.
-
Interval incidence graph coloring
PublikacjaIn 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...
-
Interval wavelength assignment in all-optical star networks
PublikacjaArtykuł 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.
-
Extended generalized blockmodeling for compound communities and external actors
PublikacjaNiektóre sieci społeczne wykazują się specyficzną strukturą wewnętrzną. W artykule rozpatrujemy społeczności, które składają się z mniejszych wspólnot. Takie społeczności nazywamy społecznościami złożonymi. Dla takich struktur zastosowalismy metodę ogólnego modelowania blokowego proponując odpowiednie rozrzerzenia dla tej metody. Wzięliśmy pod uwagę specyfikę złożonych struktur społecznych oraz ich relacje z aktorami zewnętrznymi...
-
E-mail user roles identification using OWL-based ontology approach
PublikacjaSieci społeczne jako struktury ukazujące społeczne powiązania pomiędzy osobami lub całymi organizacjami poddawane są często analizie w celu rozpoznania ról, jakie pełnią poszczególni aktorzy w danej sieci. Taka klasyfikacja ról odgrywanych przez aktorów może dostarczać wielu cennych informacji o danej sieci, gdyż daje nam całościowy obraz danej sieci pozwalając na zrozumienie, w jaki sposób sieć jest zorganizowana, i w jaki sposób...
-
Extended generalized blockmodeling for compound communities and external actors
PublikacjaWiększość sieci społecznych charakteryzuje się swoją wewnętrzną, unikatową strukturą. W artykule poddano analizie sieci społeczne złożone z wielu mniejszych grup społecznościowych, które określamy mianem złożonych sieci społecznych. Dla tego typu sieci zaproponowano rozszerzenie metody ogólnego modelowania blokowego biorąc pod uwagę specyficzną strukturę złożonych sieci społecznych oraz ich relacje z zewnętrznymi aktorami. W oparciu...
-
DBpedia and YAGO Based System for Answering Questions in Natural Language
PublikacjaIn this paper we propose a method for answering class 1 and class 2 questions (out of 5 classes defined by Moldovan for TREC conference) based on DBpedia and YAGO. Our method is based on generating dependency trees for the query. In the dependency tree we look for paths leading from the root to the named entity of interest. These paths (referenced further as fibers) are candidates for representation of actual user intention. The...
-
DBpedia and YAGO as Knowledge Base for Natural Language Based Question Answering—The Evaluation
PublikacjaThe idea of automatic question answering system has a very long history. Despite constant improvement of the systems asking questions in the natural language requires very complex solutions. In this paper the DBpedia and YAGO are evaluated as a knowledge bases for simple class 1 and 2 question answering system. For this purpose a question answering system was designed and implemented. The proposed solution and the knowledge bases...
-
The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones
PublikacjaGiven a graph G, a spanning subgraph H of G and an integer λ>=2, a λ-backbone coloring of G with backbone H is a vertex coloring of G using colors 1, 2, ..., in which the color difference between vertices adjacent in H is greater than or equal to lambda. The backbone coloring problem is to find such a coloring with maximum color that does not exceed a given limit k. In this paper, we study the backbone coloring problem for bounded-degree...
-
The computational complexity of the backbone coloring problem for planar graphs with connected backbones
PublikacjaIn the paper we study the computational complexity of the backbone coloring problem for planar graphs with connected backbones. For every possible value of integer parameters λ≥2 and k≥1 we show that the following problem: Instance: A simple planar graph GG, its connected spanning subgraph (backbone) HH. Question: Is there a λ-backbone coloring c of G with backbone H such that maxc(V(G))≤k? is either NP-complete or polynomially...
-
An O ( n log n ) algorithm for finding edge span of cacti
PublikacjaLet G=(V,E) be a nonempty graph and xi be a function. In the paper we study the computational complexity of the problem of finding vertex colorings c of G such that: (1) |c(u)-c(v)|>=xi(uv) for each edge uv of E; (2) the edge span of c, i.e. max{|c(u)-c(v)|: uv belongs to E}, is minimal. We show that the problem is NP-hard for subcubic outerplanar graphs of a very simple structure (similar to cycles) and polynomially solvable for...
-
Collaborative Data Acquisition and Learning Support
PublikacjaWith the constant development of neural networks, traditional algorithms relying on data structures lose their significance as more and more solutions are using AI rather than traditional algorithms. This in turn requires a lot of correctly annotated and informative data samples. In this paper, we propose a crowdsourcing based approach for data acquisition and tagging with support for Active Learning where the system acts as an...
-
Active Learning Based on Crowdsourced Data
PublikacjaThe paper proposes a crowdsourcing-based approach for annotated data acquisition and means to support Active Learning training approach. In the proposed solution, aimed at data engineers, the knowledge of the crowd serves as an oracle that is able to judge whether the given sample is informative or not. The proposed solution reduces the amount of work needed to annotate large sets of data. Furthermore, it allows a perpetual increase...
-
Game with a Purpose for Verification of Mappings Between Wikipedia and WordNet
PublikacjaThe paper presents a Game with a Purpose for verification of automatically generated mappings focusing on mappings between WordNet synsets and Wikipedia articles. General description of idea standing behind the games with the purpose is given. Description of TGame system, a 2D platform mobile game with verification process included in the game-play, is provided. Additional mechanisms for anti-cheating, increasing player’s motivation...
-
How to Sort Them? A Network for LEGO Bricks Classification
PublikacjaLEGO bricks are highly popular due to the ability to build almost any type of creation. This is possible thanks to availability of multiple shapes and colors of the bricks. For the smooth build process the bricks need to properly sorted and arranged. In our work we aim at creating an automated LEGO bricks sorter. With over 3700 different LEGO parts bricks classification has to be done with deep neural networks. The question arises...
-
The Backbone Coloring Problem for Bipartite Backbones
PublikacjaLet G be a simple graph, H be its spanning subgraph and λ≥2 be an integer. By a λ -backbone coloring of G with backbone H we mean any function c that assigns positive integers to vertices of G in such a way that |c(u)−c(v)|≥1 for each edge uv∈E(G) and |c(u)−c(v)|≥λ for each edge uv∈E(H) . The λ -backbone chromatic number BBCλ(G,H) is the smallest integer k such that there exists a λ -backbone coloring c of G with backbone H satisfying...
-
Evaluating Asymmetric N-Grams as Spell-Checking Mechanism
PublikacjaTypical approaches to string comparing marks two strings as either different or equal without taking into account any similarity measures. Being able to judge similarity is however required for spelling error corrections, as we want to find the best match for a given word. In this paper we present a bi2quadro-grams method for spelling errors correction. The method proposed uses different n-grams dimension for the source (checked)...
-
NLP Questions Answering Using DBpedia and YAGO
PublikacjaIn this paper, we present results of employing DBpedia and YAGO as lexical databases for answering questions formulated in the natural language. The proposed solution has been evaluated for answering class 1 and class 2 questions (out of 5 classes defined by Moldovan for TREC conference). Our method uses dependency trees generated from the user query. The trees are browsed for paths leading from the root of the tree to the question...
-
Towards Extending Wikipedia with Bidirectional Links
PublikacjaIn this paper, we present the results of our WikiLinks project which aims at extending current Wikipedia linkage mechanisms. Wikipedia has become recently one of the most important information sources on the Internet, which still is based on relatively simple linkage facilities. A WikiLinks system extends the Wikipedia with bidirectional links between fragments of articles. However, there were several attempts to introduce bidirectional...
-
Towards Facts Extraction From Texts in Polish Language
PublikacjaThe Polish language differs from English in many ways. It has more complicated conjugation and declination. Because of that automatic facts extraction from texts is difficult. In this paper we present basic differences between those languages. The paper presents an algorithm for extraction of facts from articles from Polish Wikipedia. The algorithm is based on 7 proposed facts schemes that are searched for in the analyzed text....
-
Knowledge Base Suitable for Answering Questions in Natural Language
PublikacjaThis paper presents three knowledge bases widely used by researchers coping with natural language processing: OpenCyc, DBpedia and YAGO. They are characterized from the point of view of questions answering system. In this paper a short description of the aforementioned system implementation is also presented.
-
Relation-based Wikipedia Search System for Factoid Questions Answering
PublikacjaIn this paper we propose an alternative keyword search mechanism for Wikipedia, designed as a prototype solution towards factoid questions answering. The method considers relations between articles for finding the best matching article. Unlike the standard Wikipedia search engine and also Google engine, which search the articles content independently, requiring the entire query to be satisfied by a single article, the proposed...
-
Object serialization and remote exception pattern for distributed C++/MPI application
PublikacjaMPI is commonly used standard in development of scientific applications. It focuses on interlanguage operability and is not very well object oriented. The paper proposes a general pattern enabling design of distributed and object oriented applications. It also presents its sample implementations and performance tests.
-
Parallelisation of genetic algorithms for solving university timetabling problems
PublikacjaAlgorytmy genetyczne stanowią ważną metodę rozwiązywania problemów optymalizacyjnych. W artykule skupiono się na projekcie równoległego algorytmu genetycznego pozwalającego uzyskiwać uniwersyteckie rozkłady zajęć, spełniające zarówno twarde jak i miękkie ograniczenia. Czytelnika wprowadzono w niektóre znane sposoby zrównoleglenia, przedstawiono również podejście autorów, ykorzystujące MPI. Przyjęto strukturę zarządzania opartą...
-
Spam classification methods besed on users e-mail communication graphs
PublikacjaW artykule poddano analizie grafy zbudowane w oparciu o logi serwerów pocztowych. Węzły grafów reprezentują nadawców i odbiorców wiadomości e-mail natomiast krawędzie przedstawiają procesy wymiany wiadomości e-mail. Analiza grafów pozwala na znalezienie korelacji pomiędzy topologią grafów a relacjami pomiędzy użytkownikami serwisu pocztowego. W oparciu o te relacje zaproponowano algorytm klasyfikujący wymieniane wiadomości e-mail...
-
Podstawowe mechanizmy systemu Linux w przetwarzaniu rozproszonym
PublikacjaLinux to otwarty, ciągle rozwijany system operacyjny. Dostępność kodu źródłowego oraz pełnej dokumentacji zaowocowała rozwojem wielumechanizmów wspierających przetwarzanie rozproszone. W systemie Linuxzaimplementowane zostały proste mechanizmy typu gniazda czy potoki jak i bardziej zaawansowane typu współdzielenie systemu plików czy możliwość tworzenia klastrów opartych o migracji procesów czy przekazywanie komunikatów. Narzędzia...
-
Influence and selection of basic concepts on ontology design
PublikacjaOntologies as entities representing individual point of view on surrounding world introduce heterogeneity to knowledge representation. Common set of core concepts can introduce similarity big enough for further interoperability between ontologies. In this paper an experiment is presented proving that despite differences in detail ontologies stay similar in regard of core concepts. During the experiments NOIA methodology enhanced...
-
Ontology Visualization
PublikacjaOntologie bardzo często są reprezentowane w postaci grafu, którego wierzchołkami są obiekty występujące w prezentowanej ontologii a krawędziami relacje i powiązania pomiędzy tymi obiektami. Grafy reprezentujące ontologie mogą być złożone już dla średniego rozmiaru ontologii. Stąd niezbędna jest pełna i czytelna reprezentacja elementów takiego grafu. Dostępne rozwiązania zazwyczaj nie oferują reprezentacji pełnego zbioru elementów...
-
Zespołowa budowa ontologii z wykorzystaniem systemu OCS oraz edytora Protégé
PublikacjaKonstruowanie ontologii wymaga współpracy wielu osób. W idealnej sytuacji nad pojedynczą ontologią pracować będzie duża, rozproszona społeczność tworząca tym samym wspólną reprezentację wiedzy z danej dziedziny. W publikacji zaprezentowano propozycję modelu pracy grupowej nad ontologią. Zdefiniowano model zarządzania wersjami ontologii. Przedstawiono system Ontology Creation System (OCS) oraz architekturę i implementację rozszerzenia...
-
Scenariusze ochrony własnosci intelektualnej
PublikacjaPrzedstawiono ogólnie tematykę związaną z pojęciem ochrony własności intelektualnej. W sposób szczegółowy opisano problemzwiązany ze zjawiskiem plagiaryzmu w dokumentach cyfrowych. Przedstawiono metody pozwalające na minimalizowanie skali, tak powszechnego dziś zjawiska. Opisano zarówno metody prewencyjne, jak i te związane z wykrywaniem oraz właściwym postępowaniem w przypadku wykrycia popełnienia plagiatu. Podano przykłady scenariuszy...
-
Budowa ontologii usług dla potrzeb wyszukiwania
PublikacjaOntologie, dzięki zapewnieniu formalnego opisu przy zachowaniu czytelności dla człowieka, są coraz powszechniej stosowaną metodą opisu usług sieciowych. Zaprezentowano słownik WordNet i jego zastosowanie jako meta ontologia do opisów usług podobnych różnych dostawców. Zaproponowano algorytm oparty o ten słownik umożliwiający integrację ontologii usług w celu zapewnienia interoperacyjności rozwiązań dostępnych w sieci Internet.
-
On efficient coloring of chordless graphs
PublikacjaArtykuł 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.
-
Early detection of imminent threats in social relation graphs
PublikacjaWczesne wykrywanie zagrożeń i anomalii w sieciach społecznych jest dziś prawdziwym wyzwaniem. Ludzie w realnym świecie tworzą wiele złożonych relacji społecznych, które mogą być przedstawione za pomocą grafów, w których węzły reprezentują aktorów (pojedyncze osoby lub organizacje) a krawędzie wskazują na powiązania pomiędzy nimi. Analiza nieustannie zmieniających się relacji pomiędzy aktorami może wskazać konkretne nadciągające...
-
Detection methods of dynamic spammer's behavior
PublikacjaPoczta elektroniczna ze względu na swoją naturę jest bardzo podatna na zjawisko spamu. Oddzielanie spamu od dobrych wiadomości jest zadaniem żmudnym i pracochłonnym. Dlatego jest rzeczą istotną opracowanie skutecznej metody walki ze spamem uwzględniającej nie tylko aktualne metody działania spamerów, ale również wzięcie pod uwagę dynamicznych aspektów zmieniających się stale ich zachowań.Artykuł opisuje metodę klasyfikacji wiadomości...
-
Kolorowanie końcówkowe multidrzew
PublikacjaW 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.
-
Zwarte końcówkowe kolorowanie grafów
PublikacjaPraca 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.
-
Dynamiczne zarządzanie tożsamością użytkowników w przestrzeniach inteligentnych
PublikacjaOmówiono zagadnienie uwierzytelniania oraz przedstawionoróżnice pomiędzy rozwiązaniami dostarczanymi przez systemy Linux oraz Windows. Zaprezentowano dwie metody zapewnienia centralizowanego systemu uwierzytelniającego. Obie metody były przetestowane w praktyce w sieci laboratorium komputerowego katedry KASK. Na tej podstawie wskazano metodę zdolną do zapewnienia bezpieczeństwa przestrzeni inteligentnej, w której to użytkownicy...
-
Klasyfikacja usług i ich wykorzystanie do wytwarzania aplikacji na platformie Kaskada
PublikacjaPrzedstawiono metodologię komponentowego wytwarzania aplikacji bazujących na strumieniowym przetwarzaniu danych. Scharakteryzowano proces wytwarzania oparty o nowo utworzoną platformę Kaskada, ulokowaną w środowisku superkomputera Galera. Przedstawiono gotową listę usług dostępnych na tej platformie. Podano przykładowy scenariusz orkiestracji usług z różnych kategorii, pozwalającym na skrócenie czasu wytwarzania gotowej aplikacji.
-
Lexicon Based Algorithm for Domain Ontology Merging and Alignment
PublikacjaMore and more systems contain some kind of knowledge describing their field of operation. Such knowledge in many cases is stored as an ontology. A need arises for ability to quickly match those ontologies to enable interoperability of such systems. The paper presents a lexicon based algorithm for merging and aligning of OWL ontologies. The proposed similarity levels are being presented and the proposed algorithm is being described....
-
Procedury odwzorowania i łączenia ontologii dziedzinowych
PublikacjaW trakcie prac nad rozprawą opracowano oryginalną metodę integracji ontologii na podstawie analizy leksykalnej jej elementów. Zaproponowany algorytm został zaimplementowany w postaci biblioteki w języku Java oraz włączony do systemu OCS. Opracowano również procedury i narzędzia pomocnicze wspierające proces integracji wiedzy, w tym autorską bibliotekę wizualizacji ontologii SOVA.Zaprojektowano i zaimplementowano ontologię bezpieczeństwa...