Publications
Filters
total: 118
Catalog Publications
Year 2015
-
The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones
PublicationGiven 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
PublicationIn 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...
Year 2016
-
Adaption of Open Science Paradigm at Gdańsk University of Technology
PublicationThe paper describes the basic principles standing behind Open Access and will try to dispel the doubts behind them. Further the solution adapted by the Gdańsk University of Technology is presented. Later on the systems that the University uses and means of their integration into a complex Open Science platform are described. Finally the procedures needed to publish a document in the repository alongside the University's policy...
-
An O ( n log n ) algorithm for finding edge span of cacti
PublicationLet 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...
-
Game with a Purpose for Mappings Verification
PublicationMappings 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...
-
On the hardness of computing span of subcubic graphs
PublicationIn the paper we study the problem of finding ξ-colorings with minimal span, i.e. the difference between the largest and the smallest color used.
Year 2017
-
Dobre praktyki i narzędzia open source w zwinnym wytwarzaniu oprogramowania
PublicationZwinne wytwarzanie oprogramowania stało się bardzo popularne. Na podstawie projektu MOST Wiedzy przedstawiono procesy i narzędzia wspierające wytwarzanie oprogramowania na Politechnice Gdańskiej. Metodologia DDD (domain-driven design) wspierana przez repozytorium GIT oraz tzw. proces “cherry picking” powoduje, że proces wytwarzania oprogramowania jest elastyczny i efektywny. Dodatkowo wprowadzenie elementów CI (continuous integration),...
-
Game with a Purpose for Verification of Mappings Between Wikipedia and WordNet
PublicationThe 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...
-
Techniczne aspekty niezawodnej chmury obliczeniowej
PublicationPowszechnie wykorzystuje się przetwarzanie w chmurze ze względu na redukcję kosztów zakupu sprzętu oraz łatwość zarządzania środowiskiem. W artykule zaproponowano architekturę prywatnej chmury obliczeniowej opracowanej i uruchomionej na Politechnice Gdańskiej, w ramach której wdrożono nowy portal MOST Wiedzy. Technologia wykorzystana do budowy zarówno chmury, jak i portalu wykorzystuje jedynie rozwiązania open source. Omówiono...
-
Towards facts extraction from text in Polish language
PublicationNatural 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...
Year 2018
-
Assessing Word Difficulty for Quiz-Like Game
PublicationMappings 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...
-
DBpedia and YAGO as Knowledge Base for Natural Language Based Question Answering—The Evaluation
PublicationThe 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...
-
DBpedia and YAGO Based System for Answering Questions in Natural Language
PublicationIn 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...
-
Evaluating Asymmetric N-Grams as Spell-Checking Mechanism
PublicationTypical 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)...
-
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 2019
-
2-Coloring number revisited
Publication2-Coloring number is a parameter, which is often used in the literature to bound the game chromatic number and other related parameters. However, this parameter has not been precisely studied before. In this paper we aim to fill this gap. In particular we show that the approximation of the game chromatic number by the 2-coloring number can be very poor for many graphs. Additionally we prove that the 2-coloring number may grow...
-
Crowdsourcing-Based Evaluation of Automatic References Between WordNet and Wikipedia
PublicationThe 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....
-
Exact-match Based Wikipedia-WordNet Integration
PublicationAbility to link between WordNet synsets and Wikipedia articles allows usage of those resources by computers during natural language processing. A lot of work was done in this field, however most of the approaches focus on similarity between Wikipedia articles and WordNet synsets rather than creation of perfect matches. In this paper we proposed a set of methods for automatic perfect matching generation. The proposed methods were...
Year 2020
-
Bidirectional Fragment to Fragment Links in Wikipedia
PublicationThe paper presents a WikiLinks system that extends the Wikipedia linkage model with bidirectional links between fragments of the articles and overlapping links’ anchors. The proposed model adopts some ideas from the research conducted in a field of nonlinear, computer-aided writing, often called a hypertext. WikiLinks may be considered as a web augmentation tool but it presents a new approach to the problem that addresses the specific...
-
Collaborative Data Acquisition and Learning Support
PublicationWith 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...