Search results for: NP-COMPLETENESS - Bridge of Knowledge

Search

Search results for: NP-COMPLETENESS

Search results for: NP-COMPLETENESS

  • NP-completeness of convex and weakly convex domiating set decision problems.

    Publication

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

    Full text available to download

  • Tight bounds on global edge and complete alliances in trees

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

    Full text to download in external service

  • Searching by heterogeneous agents

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

    Full text to download in external service

  • Global edge alliances in graphs

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

    Full text available to download

  • Searching by Heterogeneous Agents

    Publication

    - Year 2019

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

    Full text to download in external service

  • On Computational Aspects of Greedy Partitioning of Graphs

    Publication

    - Year 2017

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

    Full text to download in external service

  • Computational aspects of greedy partitioning of graphs

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

    Full text available to download

  • Optimization issues in distributed computing systems design

    Publication

    - Year 2014

    In 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

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

    Full text to download in external service

  • Completeness and Consistency of the System Requirement Specification

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

    Full text available to download

  • Passing from requirements specification to class model using application domain ontology

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

  • Global defensive sets in graphs

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

    Full text to download in external service

  • Fake News: Possibility of Identification in Post-Truth Media Ecology System

    Publication

    - Year 2019

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

    Full text available to download

  • THE 3D MODEL OF WATER SUPPLY NETWORK WITH APPLICATION OF THE ELEVATION DATA

    Publication

    - Year 2017

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

    Full text to download in external service

  • Information retrieval with semantic memory model

    Publication

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

    Full text to download in external service

  • Unveiling the Pool of Metallophores in Native Environments and Correlation with Their Potential Producers

    Publication
    • F. Calderón Celis
    • I. González-Álvarez
    • M. Fabjanowicz
    • S. Godin
    • L. Ouerdane
    • B. Lauga
    • R. Łobiński

    - ENVIRONMENTAL SCIENCE & TECHNOLOGY - Year 2023

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

    Full text to download in external service

  • Interval incidence graph coloring

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

    Full text available to download

  • Equitable coloring of corona products of graphs

    Publication
    • H. Furmańczyk
    • K. Kaliraj
    • M. Kubale
    • J. Vernold Vivin

    - Advances and Applications in Discrete Mathematics - Year 2013

    In 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 NP-complete even if G is 4-regular 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 4-colorable graph and H is an r-partite graph, a path, a cycle or a complete graph.

    Full text to download in external service

  • A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints

    We address a generalization of the classical 1- and 2-processor unit execution time scheduling problem on dedicated machines. In our chromatic model of scheduling machines have non-simultaneous 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...

    Full text available to download

  • Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs

    W artykule rozważamy listowo-kosztowe 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.

    Full text available to download

  • Potyczki algorytmiczne, czyli Alicja i Bogdan w różnych sytuacjach. Alicja i Bogdan w krainie czarów

    Publication

    - Pismo PG - Year 2019

    Wprowadzono w zagadnienia NP-zupełności na przykładzie problemu Suma Podzbioru

  • A note on polynomial algorithm for cost coloring of bipartite graphs with Δ ≤ 4

    In 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 n-vertex 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:...

    Full text available to download