Search
Search results for: co-np-completeness
-
NP-completeness of convex and weakly convex domiating set decision problems.
PublicationLiczby dominowania wypukłego i słabo wypukłego są nowymi rodzajami liczb dominowania. W tym artykule pokazujemy, że problemy decyzyjne dominowania wypukłegi i słabo wypukłego są NP-zupełne w przypadku grafów dwudzielnych oraz split grafów. Posługując się zmodyfikowanym algorytmem Washalla możemy w czasie wielomianowym określić, czy dany podzbiór wierzchołków grafu jest spójny bądź słabo spójny.
-
Tight bounds on global edge and complete alliances in trees
PublicationIn the talk the authors present some tight upper bounds on global edge alliance number and global complete alliance number of trees. Moreover, we present our NP-completeness results from [8] for global edge alliances and global complete alliances on subcubic bipartite graphs without pendant vertices. We discuss also polynomial time exact algorithms for finding the minimum global edge alliance on trees [7] and complete alliance...
-
Searching by heterogeneous agents
PublicationIn this work we introduce and study a pursuit-evasion game in which the search is performed by heterogeneous entities. We incorporate heterogeneity into the classical edge search problem by considering edge-labeled graphs: once a search strategy initially assigns labels to the searchers, each searcher can be only present on an edge of its own label. We prove that this problem is not monotone even for trees and we give instances...
-
Global edge alliances in graphs
PublicationIn the paper we introduce and study a new problem of finding a minimum global edge alliance in a graph which is related to the global defensive alliance (Haynes et al., 2013; Hedetniemi, 2004) and the global defensive set (Lewoń et al., 2016). We proved the NP-completeness of the global edge alliance problem for subcubic graphs and we constructed polynomial time algorithms for trees. We found the exact values of the size of the...
-
Searching by Heterogeneous Agents
PublicationIn this work we introduce and study a pursuit-evasion game in which the search is performed by heterogeneous entities. We incorporate heterogeneity into the classical edge search problem by considering edge-labeled graphs. In such setting a searcher, once a search strategy initially decides on the label of the searcher, can be present on an edge only if the label of the searcher and the label of the edge are the same. We prove...
-
On Computational Aspects of Greedy Partitioning of Graphs
PublicationIn this paper we consider a problem of graph P-coloring consisting in partitioning the vertex set of a graph such that each of the resulting sets induces a graph in a given additive, hereditary class of graphs P. We focus on partitions generated by the greedy algorithm. In particular, we show that given a graph G and an integer k deciding if the greedy algorithm outputs a P-coloring with a least k colors is NP-complete for an infinite...
-
Computational aspects of greedy partitioning of graphs
PublicationIn this paper we consider a variant of graph partitioning consisting in partitioning the vertex set of a graph into the minimum number of sets such that each of them induces a graph in hereditary class of graphs P (the problem is also known as P-coloring). We focus on the computational complexity of several problems related to greedy partitioning. In particular, we show that given a graph G and an integer k deciding if the greedy...
-
Optimization issues in distributed computing systems design
PublicationIn recent years, we observe a growing interest focused on distributed computing systems. Both industry and academia require increasing computational power to process and analyze large amount of data, including significant areas like analysis of medical data, earthquake, or weather forecast. Since distributed computing systems – similar to computer networks – are vulnerable to failures, survivability mechanisms are indispensable...
-
Interval Edge Coloring of Bipartite Graphs with Small Vertex Degrees
PublicationAn edge coloring of a graph G is called interval edge coloring if for each v ∈ V(G) the set of colors on edges incident to v forms an interval of integers. A graph G is interval colorable if there is an interval coloring of G. For an interval colorable graph G, by the interval chromatic index of G, denoted by χ'_i(G), we mean the smallest number k such that G is interval colorable with k colors. A bipartite graph G is called (α,β)-biregular...
-
Modele i algorytmy dla grafowych struktur defensywnych
PublicationW niniejszej pracy przeprowadzono analizę złożoności istnienia struktur defensywnych oraz równowag strategicznych w grafach. W przypadku struktur defensywnych badano modele koalicji defensywnych, zbiorów defensywnych i koalicji krawędziowych – każdy z nich w wersji globalnej, tj. z wymogiem dominacji całego grafu. W przypadku modeli równowagi strategicznej badano równowagę strategiczną koalicji defensywnych, równowagę strategiczną...
-
Completeness and Consistency of the System Requirement Specification
PublicationAlthough the System Requirement Specification, as a first formal and detailed document, is the base for the software project in classic software methodologies, there is a noticeable problem of assuring the completeness of this document. The lack of its completeness causes uncertainty of the project foundations. This was one of motivations for agile methodologies – if the SRS cannot be easily validated, if it can change in late project...
-
Jan Stąsiek prof. dr hab. inż.
People -
Passing from requirements specification to class model using application domain ontology
PublicationThe quality of a classic software engineering process depends on the completeness of project documents and on the inter-phase consistency. In this paper, a method for passing from the requirement specification to the class model is proposed. First, a developer browses the text of the requirements, extracts the word sequences, and places them as terms into the glossary. Next, the internal ontology logic for the glossary needs to...
-
Magdalena Szuflita-Żurawska
PeopleHead of the Scientific and Technical Information Services at the Gdansk University of Technology Library and the Leader of the Open Science Competence Center. She is also a Plenipotentiary of the Rector of the Gdańsk University of Technology for open science. She is a PhD Candidate. Her main areas of research and interests include research productivity, motivation, management of HEs, Open Access, Open Research Data, information...
-
Sources of Market Information, Its Quality and New Product Financial Performance
PublicationWhile we observe a growing interest in the role of market information in new product development (NPD), existing research has still largely ignored the quality of market information that is a crucial issue in the era of the information society. What does affect the quality of market information in new product development projects, and how does this quality influence the financial performance of new products? In this paper, we address...
-
Marek Czachor prof. dr hab.
People -
Reliability of Pulse Measurements in Videoplethysmography
PublicationReliable, remote pulse rate measurement is potentially very important for medical diagnostics and screening. In this paper the Videoplethysmography was analyzed especially to verify the possible use of signals obtained for the YUV color model in order to estimate the pulse rate, to examine what is the best pulse estimation method for short video sequences and finally, to analyze how potential PPG-signals can be distinguished from...
-
Aleksandra Giełdoń - Paszek dr hab.
PeopleDoktor habilitowany w dziedzinie nauk o sztuce, historyk sztuki. Studiowała historię sztuki na Wydziale Filozoficzno-Historycznym Uniwersytetu Jagiellońskiego w Krakowie. W roku 2002 na Wydziale Historycznym tejże uczelni uzyskała tytuł doktora nauk humanistycznych w zakresie nauk o sztuce na podstawie dysertacji: Malarstwo pejzażowe a szkolnictwo artystyczne w Polsce (do 1939 roku). W roku 2015 została doktorem habilitowanym w...
-
Zdolni z Pomorza 2019/20 - Nieco więcej o kwasach i zasadach
e-Learning CoursesCel kursu: Celem kursu jest zaznajomienie uczestników z teoriami kwasów i zasad, podstawami równowagi chemicznej oraz skalą pH. Opis kursu: Pojęcie kwasów i zasad jest wprowadzane już na wczesnych etapach edukacji, jednak okazuje się, że teorii wyjaśniających, co jest kwasem, a co zasadą jest wiele. Jak np. wyjaśnić, że chlorek glinu AlCl₃ można uznać za kwas, skoro nie posiada on atomów wodoru? W trakcie kursu poznamy teorię...
-
Zdolni z Pomorza 2020/21 - Matrix reaktywacja
e-Learning CoursesCel kursu: Celem kursu jest zapoznanie uczniów z pojęciami takimi jak: - macierze i wyznaczniki, - układy równań liniowych. Opis kursu: Istnieje wiele żartów o matematykach i dziedzinach matematyki. Choćby poniższe: Idą sobie dwie macierze kwadratowe. Nagle jedna upadła: -Nic ci nie jest?-pyta druga macierz -Nic. Tylko się odwróciłam. Co to jest macierz Kanaka? Macierz k x k. Jak wszystkim wiadomo w każdej anegdocie jest zawsze...
-
Distance learning trends: introducing new solutions to data analysis courses
PublicationNowadays data analysis of any kind becomes a piece of art. The same happens with the teaching processes of statistics, econometrics and other related courses. This is not only because we are facing (and are forced to) teach online or in a hybrid mode. Students expect to see not only the theoretical part of the study and solve some practical examples together with the instructor. They are waiting to see a variety of tools, tutorials,...
-
Fake News: Possibility of Identification in Post-Truth Media Ecology System
PublicationInformation comes as basic good which affects social well-being. A modern society and a modern state – its administration, education, culture, national economy and armed forces – cannot function efficiently without a rationally developed field of information. The quality of the functioning of that system depends on a specific feature of information, that is namely: its reliability which makes it possible for us to evaluate accuracy,...
-
Information retrieval with semantic memory model
PublicationPsycholinguistic theories of semantic memory form the basis of understanding of natural language concepts. These theories are used here as an inspiration for implementing a computational model of semantic memory in the form of semantic network. Combining this network with a vector-based object-relation-feature value representation of concepts that includes also weights for confidence and support, allows for recognition of concepts...
-
Unveiling the Pool of Metallophores in Native Environments and Correlation with Their Potential Producers
PublicationFor many organisms, metallophores are essential biogenic ligands that ensure metal scavenging and acquisition from their environment. Their identification is challenging in highly organic matter rich environments like peatlands due to low solubilization and metal scarcity and high matrix complexity. In contrast to common approaches based on sample modification by spiking of metal isotope tags, we have developed a two-dimensional...
-
THE 3D MODEL OF WATER SUPPLY NETWORK WITH APPLICATION OF THE ELEVATION DATA
Publication3D visualization is a key element of research and analysis and as the source used by experts in various fields e.g.: experts from water and sewage systems. The aim of this study was to visualize in three-dimensional space model of water supply network with relief. The path of technological development of GESUT data (Geodezyjna Ewidencja Sieci Uzbrojenia Terenu – geodetic records of public utilities) for water supply and measurement...
-
Karol Grębowski dr inż.
PeopleKarol Grębowski (M.Sc.) works as an assistant at the Department of Technical Fundamentals of Architecture Design of the Faculty of Architecture at Gdansk University of Technology. His scientific research deals with dynamic phenomena occurring during the vibration of structures, bridges, and studies the design methodology of the elements forming passive protection system of the vehicles degraded by struck or explosion in the context...
-
Elementy prawa autorskiego (szkolenie zewnętrzne)
e-Learning CoursesCELSzkolenie ma na celu wyjaśnienie uczestnikom trudnych kwestii związanych z prawem autorskim. Pozwolina uporządkowanie i zapoznanie się z terminologią prawniczą, która często występuje np. w umowachwydawniczych. OPISSzkolenie z elementów prawa autorskiego dla naukowców przybliży tematykę związaną z ochroną danych ikorzystaniem z publikacji naukowych. Tematy podjęte w ramach szkolenia: ochrona twórczości iprowadzonych badań;...
-
Zdolni z Pomorza 2018/19 - Elementy algebry liniowej
e-Learning CoursesCel kursu: Celem kursu jest zapoznanie uczniów z pojęciami takimi jak: - liczby zespolone, - macierze i wyznaczniki, - układy równań liniowych. Opis kursu: Istnieje wiele żartów o matematykach i dziedzinach matematyki. Choćby poniższe: Przychodzi „i” do lekarza, a lekarz mówi: Coś się pani uroiło! Idą sobie dwie macierze kwadratowe. Nagle jedna upadła: -Nic ci nie jest?-pyta druga macierz -Nic. Tylko się odwróciłam. Co...
-
NEW PRODUCT DEVELOPMENT FROM THE PERSPECTIVE OF CREATING A COMPETITIVE ADVANTAGE
PublicationIt is acknowledged that achieving product-based competitive advantage is a key task for a company. However, there is still a research gap in determining those specific actions in the process of developing new products that arise from companies' efforts to achieve product-based competitive advantage. Therefore, the aim of this study is to determine the specific actions in the new product development (NPD) process that result from...
-
Ranking of Generation Source Locations by a Hybrid Multi-Criteria Method
PublicationThe paper presents a ranking of the locations of eight renewable energy sources (RES) made using a hybrid multi-criteria analysis method. The method is a combination of the analytical hierarchical process (AHP) method and numerical taxonomy. The considered generating sources, i.e. solar plants, biogas plants, and wind farms are sources that will significantly contribute to implementing the provisions of the energy and climate package...
-
Ecology In Tribology: Selected Problems of Eliminating Natural Oil-Based Lubricants from Machine Friction Couples
PublicationThe elimination of mineral oil-based lubricants from machines has multiple beneficial effects on the natural environment. Firstly – these lubricants are a direct threat to the environment in the event of leaks; secondly – their elimination reduces the demand for crude oil from which they are obtained. In addition, in many cases, e.g. when replacing traditional lubricants with water, friction losses in the bearings can also be reduced...
-
Assessing Tram Infrastructure Safety Using the Example of the City of Gdańsk
PublicationAnalysis of Gdańsk’s tram network statistics shows that incidents are quite frequent (about 650 within 5 years) and mostly involve collisions and crashes. As well as reducing the tram systems’ efficiency and reliability, incidents have a nega-tive effect on road safety. As Polish cities extend their tram networks, they must also ensure that their existing networks are safe. This is to be achieved by conducting safety assessments....
-
Global defensive sets in graphs
PublicationIn the paper we study a new problem of finding a minimum global defensive set in a graph which is a generalization of the global alliance problem. For a given graph G and a subset S of a vertex set of G, we define for every subset X of S the predicate SEC ( X ) = true if and only if | N [ X ] ∩ S | ≥ | N [ X ] \ S | holds, where N [ X ] is a closed neighbourhood of X in graph G. A set S is a defensive alliance if and only if for...
-
Katarzyna Stankiewicz dr
People -
Technologie remediacji środowiska
e-Learning CoursesRozwój przemysłowo-gospodarczy i rozwój infrastruktury oraz wzrost standardu życia mieszkańców każdego kraju nieodzownie niosą za sobą powstawanie rosnących ilości różnego rodzaju ścieków oraz odpadów przemysłowych i komunalnych. To z kolei przyczynia się do postępującego zanieczyszczenia i degradacji środowiska, w tym szczególnie podłoża gruntowego. Stąd niezwykle istotne jest zapobieganie zanieczyszczeniom poprzez projektowanie...
-
Beata Krawczyk-Bryłka dr
PeoplePsycholog, doktor nauk humanistycznych w dziedzinie zarządzania, adiunkt w Katedrze przedsiębiorczości. 2018 - 2021: Kierownik projektu NCN: „Efektuacyjny model zespołu przedsiębiorczego. Jak działają przedsiębiorcze zespoły odnoszące sukces" od 2016: Quality Standards Lead filaru People management & personal development na studiach MBA Politechniki Gdańskiej 2008 – 2012: Prodziekan ds kształcenia Wzydziału Zarządzania i Ekonomii...
-
Historia Architektury Powszechnej II 2022/2023
e-Learning CoursesKURS HISTORII ARCHITEKTURY POWSZECHNEJ II (HAPow II) jest kursem obowiązkowym na 2 semestrze studiów I stopnia (inżynierskich) na Wydziale Architektury PG. Trwa cały semestr i zakończony jest egzaminem. Składa się z piętnastu jednogodzinnych wykładów oraz siedmiu odbywających się co 2 tygodnie dwugodzinnych ćwiczeń. Tematyka kursu obejmuje historię architektury świata zachodniego w epoce Nowożytności, począwszy od czasów renesansu...
-
Zdolni z Pomorza 2022/23 - Podstawy programowania urządzeń brzegowych na Raspberry Pi w języku Python
e-Learning CoursesCel kursu: Celem kursu jest zapoznanie uczniów z podstawami w zakresie programowania w języku Python w tym urządzeń brzegowych podłączanych do minikomputera Raspberry Pi 4B, umożliwiających pomiar wielkości fizycznych, środowiskowych lub biomedycznych. Opis kursu: Python jest jednym z najpopularniejszych języków programowania, który wraz w połączeniu z dodatkowymi narzędziami może posłużyć do tworzenia stron internetowych, przetwarzania...
-
Zdolni z Pomorza 2022/23 - Podstawy programowania urządzeń brzegowych na Raspberry Pi w języku Python - arch.
e-Learning CoursesCel kursu: Celem kursu jest zapoznanie uczniów z podstawami w zakresie programowania w języku Python w tym urządzeń brzegowych podłączanych do minikomputera Raspberry Pi 4B, umożliwiających pomiar wielkości fizycznych, środowiskowych lub biomedycznych. Opis kursu: Python jest jednym z najpopularniejszych języków programowania, który wraz w połączeniu z dodatkowymi narzędziami może posłużyć do tworzenia stron internetowych, przetwarzania...
-
Graph security testing
PublicationSet S ⊂ V is called secure set iff ∀ X ⊂ S | N [ X ] ∩ S | ≥ | N ( X ) \ S | [3]. That means that every subset of a secure set has at least as many friends (neighbour vertices in S) as enemies (neighbour vertices outside S) and will be defended in case of attack. Problem of determining if given set is secure is co −NP -complete, there is no efficient algorithm solving it [3]. Property testers are algorithms that distinguish inputs...
-
Projektowanie urbanistyczne IV
e-Learning CoursesZadanie polega na przygotowaniu projektu zagospodarowania działki na obszarze osiedla Garnizon w Gdańsku Wrzeszczu. W projekcie należy również przyjąć funkcję publiczną o dowolnej skali. Unikatowym aspektem było powiązanie w jednym projekcie wiedzy z zakresu kilku dziedzin, które w praktyce nie są wdrażane przez jednego projektanta, lecz realizowane w ramach osobnych specjalizacji: projektowania architektoniczno-urbanistycznego,...
-
Techniki plastyczne i prezentacyjne 2023
e-Learning CoursesCelem zajęć jest zapoznanie studentów z różnorodnymi technikami plastycznymi stosowanymi do prezentacji opracowań studyjnych i projektów w różnych fazach. Zajęcia odbywają się w trybie stacjonarnym w Sali 365 we wtorki Grupa I. od 11:15 do 13:00 Grupa II. od 13:15 do 15:00 Pracujemy na formacie poziomym A4 papieru rysunkowego o grub. minimum 160g. Prace graficzne umieszczamy przy prawej krawędzi. Margines wokół arkusza 1cm,...