Wyniki wyszukiwania dla: COST COLORING - MOST Wiedzy

Wyszukiwarka

Wyniki wyszukiwania dla: COST COLORING

Wyniki wyszukiwania dla: COST COLORING

  • Chromatic cost coloring of weighted bipartite graphs

    Given a graph G and a sequence of color costs C, the Cost Coloring optimization problem consists in finding a coloring of G with the smallest total cost with respect to C. We present an analysis of this problem with respect to weighted bipartite graphs. We specify for which finite sequences of color costs the problem is NP-hard and we present an exact polynomial algorithm for the other finite sequences. These results are then extended...

    Pełny tekst do pobrania w serwisie zewnętrznym

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

    Pełny tekst do pobrania w portalu

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

    Pełny tekst do pobrania w portalu

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

    Publikacja

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Efficient List Cost Coloring of Vertices and∕or Edges of Some Sparse Graphs

    Publikacja

    - Rok 2007

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Efficient list cost coloring of vertices and/or edges of some sparse graphs

    Publikacja

    - Rok 2007

    Rozważane jest kolorowanie wierzchołków i krawędzi grafów w modelach klasycznym, totalnym i pseudototalnym z uwzględnieniem dodatkowego ograniczenia w postaci list dostępnych kolorów. Proponujemy wielomianowy algorytm oparty na paradygmacie programowania dynamicznego dla grafów o strukturze drzewa. Wynik ten można uogólnić na grafy o liczbie cyklomatycznej ograniczonej z góry przez dowolnie wybraną stała.

  • Eqiuitable coloring of corona products of cubic graphs is harder than ordinary coloring

    A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G. In this paper the problem of determinig the equitable coloring number for coronas of cubic graphs is studied. Although the problem of ordinary coloring of coronas...

    Pełny tekst do pobrania w portalu

  • Interval incidence coloring of subcubic graphs

    In this paper we study the problem of interval incidence coloring of subcubic graphs. In [14] the authors proved that the interval incidence 4-coloring problem is polynomially solvable and the interval incidence 5-coloring problem is N P-complete, and they asked if χii(G) ≤ 2∆(G) holds for an arbitrary graph G. In this paper, we prove that an interval incidence 6-coloring always exists for any subcubic graph G with ∆(G) = 3.

    Pełny tekst do pobrania w portalu

  • The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones

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

    Pełny tekst do pobrania w serwisie zewnętrznym

  • On-line P-coloring of graphs

    For a given induced hereditary property P, a P-coloring of a graph G is an assignment of one color to each vertex such that the subgraphs induced by each of the color classes have property P. We consider the effectiveness of on-line P-coloring algorithms and give the generalizations and extensions of selected results known for on-line proper coloring algorithms. We prove a linear lower bound for the performance guarantee function...

    Pełny tekst do pobrania w portalu

  • Interval incidence coloring of bipartite graphs

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

    Pełny tekst do pobrania w portalu

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

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs

    Publikacja

    - Rok 2016

    In this paper we consider the complexity of semi-equitable k-coloring of the vertices of a cubic or subcubic graph. We show that, given n-vertex subcubic graph G, a semi-equitable k-coloring of G is NP-hard if s >= 7n/20 and polynomially solvable if s <= 7n/21, where s is the size of maximum color class of the coloring.

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Equitable coloring of graphs. Recent theoretical results and new practical algorithms

    Publikacja

    In this paper we survey recent theoretical results concerning conditions for equitable colorability of some graphs and recent theoretical results concerning the complexity of equitable coloring problem. Next, since the general coloring problem is strongly NP-hard, we report on practical experiments with some efficient polynomial-time algorithms for approximate equitable coloring of general graphs.

    Pełny tekst do pobrania w portalu

  • Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling

    In the paper we consider the problems of equitable and semi-equitable coloring of vertices of cubic graphs. We show that in contrast to the equitable coloring, which is easy, the problem of semi-equitable coloring is NP- complete within a broad spectrum of graph parameters. This affects the complexity of batch scheduling of unit-length jobs with cubic incompatibility graph on three uniform processors to minimize...

    Pełny tekst do pobrania w portalu

  • Dynamic F-free Coloring of Graphs

    Publikacja

    - GRAPHS AND COMBINATORICS - Rok 2018

    A problem of graph F-free coloring consists in partitioning the vertex set of a graph such that none of the resulting sets induces a graph containing a fixed graph F as an induced subgraph. In this paper we consider dynamic F-free coloring in which, similarly as in online coloring, the graph to be colored is not known in advance; it is gradually revealed to the coloring algorithm that has to color each vertex upon request as well...

    Pełny tekst do pobrania w portalu

  • No-Wait & No-Idle Open Shop Minimum Makespan Scheduling with Bioperational Jobs

    In the open shop scheduling with bioperational jobs each job consists of two unit operations with a delay between the end of the first operation and the beginning of the second one. No-wait requirement enforces that the delay between operations is equal to 0. No-idle means that there is no idle time on any machine. We model this problem by the interval incidentor (1, 1)-coloring (IIR(1, 1)-coloring) of a graph with the minimum...

    Pełny tekst do pobrania w portalu

  • 2-Coloring number revisited

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

    Pełny tekst do pobrania w portalu

  • Optimal backbone coloring of split graphs with matching backbones

    For a graph G with a given subgraph H, the backbone coloring is defined as the mapping c: V(G) -> N+ such that |c(u)-c(v)| >= 2 for each edge uv \in E(H) and |c(u)-c(v)| >= 1 for each edge uv \in E(G). The backbone chromatic number BBC(G;H) is the smallest integer k such that there exists a backbone coloring with max c(V(G)) = k. In this paper, we present the algorithm for the backbone coloring of split graphs with matching backbone.

    Pełny tekst do pobrania w portalu

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

    Pełny tekst do pobrania w portalu

  • On Computational Aspects of Greedy Partitioning of Graphs

    Publikacja

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

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Equitable coloring of corona multiproducts of graphs

    Publikacja

    - Discussiones Mathematicae Graph Theory - Rok 2017

    We give some results regarding the equitable chromatic number for l-corona product of two graphs: G and H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G.

    Pełny tekst do pobrania w portalu

  • The Backbone Coloring Problem for Small Graphs

    In this paper we investigate the values of the backbone chromatic number, derived from a mathematical model for the problem of minimization of bandwidth in radio networks, for small connected graphs and connected backbones (up to 7 vertices). We study the relationship of this parameter with the structure of the graph and compare the results with the solutions obtained using the classical graph coloring algorithms (LF, IS), modified...

    Pełny tekst do pobrania w serwisie zewnętrznym

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

    Pełny tekst do pobrania w portalu

  • Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs

    Publikacja

    - DISCRETE APPLIED MATHEMATICS - Rok 2018

    We consider the complexity of semi-equitable k-coloring, k>3, of the vertices of a cubic or subcubic graph G. In particular, we show that, given a n-vertex subcubic graph G, it is NP-complete to obtain a semi-equitable k-coloring of G whose non-equitable color class is of size s if s>n/3, and it is polynomially solvable if s, n/3.

    Pełny tekst do pobrania w portalu

  • Parallel tabu search for graph coloring problem

    Publikacja

    Tabu search is a simple, yet powerful meta-heuristic based on local search that has been often used to solve combinatorial optimization problems like the graph coloring problem. This paper presents current taxonomy of patallel tabu search algorithms and compares three parallelization techniques applied to Tabucol, a sequential TS algorithm for graph coloring. The experimental results are based on graphs available from the DIMACS...

  • Dynamic coloring of graphs

    Publikacja

    - FUNDAMENTA INFORMATICAE - Rok 2012

    Dynamics is an inherent feature of many real life systems so it is natural to define and investigate the properties of models that reflect their dynamic nature. Dynamic graph colorings can be naturally applied in system modeling, e.g. for scheduling threads of parallel programs, time sharing in wireless networks, session scheduling in high-speed LAN's, channel assignment in WDM optical networks as well as traffic scheduling. In...

  • The Backbone Coloring Problem for Bipartite Backbones

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

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Colorings of the Strong Product of Circulant Graphs

    Publikacja
    • M. Jurkiewicz

    - Rok 2012

    Graph coloring is one of the famous problems in graph theory and it has many applications to information theory. In the paper we present colorings of the strong product of several circulant graphs.

  • Better polynomial algorithms for scheduling unit-length jobs with bipartite incompatibility graphs on uniform machines

    The goal of this paper is to explore and to provide tools for the investigation of the problems of unit-length scheduling of incompatible jobs on uniform machines. We present two new algorithms that are a significant improvement over the known algorithms. The first one is Algorithm 2 which is 2-approximate for the problem Qm|p j = 1, G = bisubquartic|Cmax . The second one is Algorithm 3 which is 4-approximate for the problem Qm|p...

    Pełny tekst do pobrania w portalu

  • Minimum order of graphs with given coloring parameters

    Publikacja

    - DISCRETE MATHEMATICS - Rok 2015

    A complete k-coloring of a graph G=(V,E) is an assignment F: V -> {1,...,k} of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively investigated graph invariants related to complete colorings are the minimum and maximum number of colors in a complete coloring (chromatic number χ(G) and achromatic number ψ(G), respectively),...

    Pełny tekst do pobrania w portalu

  • On incidence coloring of coloring of complete multipartite and semicubic bipartite graphs

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

    Pełny tekst do pobrania w portalu

  • Scheduling of compatible jobs on parallel machines

    Publikacja

    - Rok 2021

    The dissertation discusses the problems of scheduling compatible jobs on parallel machines. Some jobs are incompatible, which is modeled as a binary relation on the set of jobs; the relation is often modeled by an incompatibility graph. We consider two models of machines. The first model, more emphasized in the thesis, is a classical model of scheduling, where each machine does one job at time. The second one is a model of p-batching...

  • Equitable colorings of some variation of corona products of cubic graphs

    Publikacja

    - Archives of Control Sciences - Rok 2024

    The problem of determining the value of equitable chromatic number for multicoronas of cubic graphs is studied. We provide some polynomially solvable cases of cubical multicoronas and give simple linear time algorithms for equitable coloring of such graphs which use almost optimal number of colors in the remaining cases.

    Pełny tekst do pobrania w portalu

  • The computational complexity of the backbone coloring problem for planar graphs with connected backbones

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

    Pełny tekst do pobrania w portalu

  • Parallel immune system for graph coloring

    Publikacja

    - Rok 2008

    This paper presents a parallel artificial immune system designed forgraph coloring. The algorithm is based on the clonal selection principle. Each processor operates on its own pool of antibodies and amigration mechanism is used to allow processors to exchange information. Experimental results show that migration improves the performance of the algorithm. The experiments were performed using a high performance cluster on a set...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Computer experiments with a parallel clonal selection algorithm for the graph coloring problem

    Publikacja

    Artificial immune systems (AIS) are algorithms that are based on the structure and mechanisms of the vertebrate immune system. Clonal selection is a process that allows lymphocytes to launch a quick response to known pathogens and to adapt to new, previously unencountered ones. This paper presents a parallel island model algorithm based on the clonal selection principles for solving the Graph Coloring Problem. The performance of...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Equitable coloring of hypergraphs

    Publikacja

    - DISCRETE APPLIED MATHEMATICS - Rok 2019

    A hypergraph is equitablyk-colorable if its vertices can be partitioned into k sets/colorclasses in such a way that monochromatic edges are avoided and the number of verticesin any two color classes differs by at most one. We prove that the problem of equitable 2-coloring of hypergraphs is NP-complete even for 3-uniform hyperstars. Finally, we apply the method of dynamic programming for designing a polynomial-time algorithm to...

    Pełny tekst do pobrania w portalu

  • Infinite chromatic games

    In the paper we introduce a new variant of the graph coloring game and a new graph parameter being the result of the new game. We study their properties and get some lower and upper bounds, exact values for complete multipartite graphs and optimal, often polynomial-time strategies for both players provided that the game is played on a graph with an odd number of vertices. At the end we show that both games, the new and the classic...

    Pełny tekst do pobrania w portalu

  • Equitable coloring of corona products of graphs

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

    - Advances and Applications in Discrete Mathematics - Rok 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.

    Pełny tekst do pobrania w portalu

  • Rearrangeability in multicast Clos networks is NP-complete

    Publikacja

    Przestrajalność w polach Closa z połączeniami jeden do jeden jest problemem wielomianowym. W pracy pokazano, że w polach z połączeniami jeden do wiele problem ten jest NP zupełny.Three-stage elos networks are commutation networks with circuit switching. So far, graph theory has been very useful tool for solving issues related to these networks with unicast connections. This is so because if elos network is represented as a bipartite...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • A bound on the number of middle-stage crossbars in f-cast rearrangeable Clos networks

    Publikacja

    - Rok 2015

    In 2006 Chen and Hwang gave a necessary and sufficient condition under which a three-stage Clos network is rearrangeable for broadcast connections. Assuming that only crossbars of the first stage have no fan-out property, we give similar conditions for f-cast Clos networks, where f is an arbitrary but fixed invariant of the network. Such assumptions are valid for some practical switching systems, e.g. high-speed crossconnects....

  • IZOLACJA I IDENTYFIKACJA NATURALNYCH SUBSTANCJI BARWIĄCYCH OBECNYCH W PRÓBKACH FARB ARTYSTYCZNYCH I TKANINACH POCHODZENIA HISTORYCZNEGO

    Natural organic dyes are group of substances that belong to various types of chemical compounds. The most commonly used in paintings and dyeing textiles were naturally occurring dyestuffs from group of anthraquinones, flavones and indigoid dyes. Identification of coloring substances present in historical artistic paints provides relevant information for a wide range of specialists dealing with works of art and in the field of conservation science....

    Pełny tekst do pobrania w serwisie zewnętrznym

  • The Effect of Full-Cell Impregnation of Pine Wood (Pinus sylvestris L.) on Changes in Electrical Resistance and on the Accuracy of Moisture Content Measurement Using Resistance Meters

    Publikacja

    - BIORESOURCES - Rok 2018

    The impact of the full-cell impregnation of pine wood was investigated with respect to changes in electrical resistance and the accuracy of moisture content measurement. This study compared the resistance of impregnated and untreated pine timber harvested from the northern part of Poland (Pomeranian region). The wood was impregnated by the vacuum-pressure method. The preservative (TANALITH E 3475) and coloring (TANATONE 3950) agents...

    Pełny tekst do pobrania w portalu

  • Towards the boundary between easy and hard control problems in multicast Clos networks

    In this article we study 3-stage Clos networks with multicast calls in general and 2-cast calls, in particular. We investigate various sizes of input and output switches and discuss some routing problems involved in blocking states. To express our results in a formal way we introduce a model of hypergraph edge-coloring. A new class of bipartite hypergraphs corresponding to Clos networks is studied. We identify some polynomially...

    Pełny tekst do pobrania w portalu

  • On some Zarankiewicz numbers and bipartite Ramsey Numbers for Quadrilateral

    Publikacja

    - ARS COMBINATORIA - Rok 2015

    The Zarankiewicz number z ( m, n ; s, t ) is the maximum number of edges in a subgraph of K m,n that does not contain K s,t as a subgraph. The bipartite Ramsey number b ( n 1 , · · · , n k ) is the least positive integer b such that any coloring of the edges of K b,b with k colors will result in a monochromatic copy of K n i ,n i in the i -th color, for some i , 1 ≤ i ≤ k . If n i = m for all i , then we denote this number by b k ( m )....

    Pełny tekst do pobrania w portalu

  • Copper Slag as a Potential Waste Filler for Polyethylene-Based Composites Manufacturing

    Publikacja

    - Tanzania Journal of Science - Rok 2021

    The present study aimed to analyze the application of waste material from copper production– copper slag (ŻŻL) as filler for composites based on the high-density polyethylene (HDPE). Copper slag filler was introduced in the amounts of 1–20 wt%, and its influence on the appearance (color analysis), chemical structure (Fourier-transform infrared (FTIR) spectroscopy), microstructure (optical microscopy), as well as static (tensile...

    Pełny tekst do pobrania w portalu

  • Methodology for Text Classification using Manually Created Corpora-based Sentiment Dictionary

    Publikacja

    - Rok 2018

    This paper presents the methodology of Textual Content Classification, which is based on a combination of algorithms: preliminary formation of a contextual framework for the texts in particular problem area; manual creation of the Hierarchical Sentiment Dictionary (HSD) on the basis of a topically-oriented Corpus; tonality texts recognition via using HSD for analysing the documents as a collection of topically completed fragments...

    Pełny tekst do pobrania w portalu

  • T-colorings, divisibility and circular chromatic number

    Let T be a T-set, i.e., a finite set of nonnegative integers satisfying 0 ∈ T, and G be a graph. In the paper we study relations between the T-edge spans espT (G) and espd⊙T (G), where d is a positive integer and d ⊙ T = {0 ≤ t ≤ d (max T + 1): d |t ⇒ t/d ∈ T} . We show that espd⊙T (G) = d espT (G) − r, where r, 0 ≤ r ≤ d − 1, is an integer that depends on T and G. Next we focus on the case T = {0} and show that espd⊙{0} (G) =...

    Pełny tekst do pobrania w portalu

  • Approximation algorithms for job scheduling with block-type conflict graphs

    Publikacja

    - COMPUTERS & OPERATIONS RESEARCH - Rok 2024

    The problem of scheduling jobs on parallel machines (identical, uniform, or unrelated), under incompatibility relation modeled as a block graph, under the makespan optimality criterion, is considered in this paper. No two jobs that are in the relation (equivalently in the same block) may be scheduled on the same machine in this model. The presented model stems from a well-established line of research combining scheduling theory...

    Pełny tekst do pobrania w serwisie zewnętrznym