Search results for: NPCOMPLETENESS

NPcompleteness 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ą NPzupeł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 NPcompleteness 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 pursuitevasion game in which the search is performed by heterogeneous entities. We incorporate heterogeneity into the classical edge search problem by considering edgelabeled 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 NPcompleteness 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 pursuitevasion game in which the search is performed by heterogeneous entities. We incorporate heterogeneity into the classical edge search problem by considering edgelabeled 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 Pcoloring 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 Pcoloring with a least k colors is NPcomplete 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 Pcoloring). 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 Speciﬁcation, as a ﬁrst 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...

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 interphase 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...

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...

Fake News: Possibility of Identification in PostTruth Media Ecology System
PublicationInformation comes as basic good which affects social wellbeing. 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 vectorbased objectrelationfeature value representation of concepts that includes also weights for confidence and support, allows for recognition of concepts...

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 threedimensional 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...

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 twodimensional...

A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints
PublicationWe address a generalization of the classical 1 and 2processor unit execution time scheduling problem on dedicated machines. In our chromatic model of scheduling machines have nonsimultaneous availability times and tasks have arbitrary release times and due dates. Also, the versatility of our approach makes it possible to generalize all known classical criteria of optimality. Under these stipulations we show that the problem...

Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
PublicationW artykule rozważamy listowokosztowe 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.

Equitable coloring of corona products of graphs
PublicationIn this paper we consider an equitable coloring of some corona products of graphs G and H in symbols, G o H). In particular, we show that deciding the colorability of G o H is NPcomplete even if G is 4regular and H is K_2. Next, we prove exact values or upper bounds on the equitable chromatic number of G o H, where G is an equitably 3 or 4colorable graph and H is an rpartite graph, a path, a cycle or a complete graph.

Potyczki algorytmiczne, czyli Alicja i Bogdan w różnych sytuacjach. Alicja i Bogdan w krainie czarów
PublicationWprowadzono w zagadnienia NPzupełności na przykładzie problemu Suma Podzbioru

Interval incidence graph coloring
PublicationIn 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 kpartite graphs. We also study the complexity of the...

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 nvertex 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:...