Wyniki wyszukiwania dla: GRAPH COLORING - MOST Wiedzy

Wyszukiwarka

Wyniki wyszukiwania dla: GRAPH COLORING

Wyniki wyszukiwania dla: GRAPH COLORING

  • Koala graph coloring library: an open graph coloring library for real-world applications

    Publikacja

    Pomimo intensywnej pracy naukowej na polu kolorowania grafów, nie jest znana kompletna i dedykowana biblioteka programistyczna. Celem artykułu jest zaproponowanie architektury takiej biblioteki. Celem jest spełnienie oczekiwań wypływających z rzeczywistych zastosowań, w szczególności spełnienie potrzeb wydajnościowych. Zaimplementowano szereg algorytmów cheurystycznego kolorowania grafów. Przyjętym językiem programowania jest C++....

    Pełny tekst do pobrania w serwisie zewnętrznym

  • 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

  • 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

  • On greedy graph coloring in the distributed model

    Publikacja

    Artykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Zaprezentowano nowy probabilistyczny algorytm dający w wyniku pokolorowanie LF. Udowodniono, że jakakolwiek rozproszona implementacja LF wymaga co najmniej D rund, gdzie D jest maksymalnym stopniem wierzchołka w grafie.

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

  • A better practical algorithm for distributed graph coloring

    Publikacja

    - Rok 2002

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Distributed largest-first algorithm for graph coloring.

    Publikacja

    - Rok 2004

    W artykule zaprezentowano rozproszony, probabilistyczny algorytm kolorowania grafów. Kolorowanie uzyskane jest optymalne lub prawie optymalne dla takich klas grafów jak koła dwudzielne, gąsienice czy korony. Udowodniono, że algorytm ten działa w czasie O(D^2 log n) rund dla dowolnego grafu n wierzchołkowegoo stopniu maksymalnym D.

  • An experimental study of distributed algorithms for graph coloring.

    W pracy podano algorytm rozproszonego kolorowania grafówi porównano ze znanym wcześniej algorytmem.

  • On the complexity of distributed graph coloring with local minimality constraints

    Publikacja

    - NETWORKS - Rok 2009

    Artykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Omówiono algorytmy rozproszone, dające w wyniku pokolorowanie spełniające warunki dla pokolorowań sekwencyjnych typu S oraz Largest-First (LF). Udowodniono również, że każda rozproszona implementacja algorytmu S wymaga co najmniej Omega(log n / log log n) rund, a algorytmu LF co najmniej Omega (n^{1/2}) rund, gdzie n oznacza liczbę wierzchołków grafu.

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Greedy algorithms for backbone graph coloring in KOALA library

    Publikacja

    - Rok 2012

  • Self-stabilizing algorithms for graph coloring with improved performance guarantees

    Publikacja

    W pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm kolorowania grafów oparty na konstrukcji drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm z gwarantowaną wielomianową liczbą ruchów, który dokładnie koloruje grafy dwudzielne.

  • 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

  • Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.

    Publikacja

    - Rok 2008

    W pracy rozważono problem kolorowania grafów mieszanych, opisujący zagadnienie szeregowania zadań, w którym zależności czasowe zadań mają charakter częściowego porządku lub wzajemnego wykluczania. Dla przypadku, w którym graf zależności jest szeregowo-równoległy, podano algorytm rozwiązujący problem optymalnie w czasie $O(n^3.376 * log n)$.

    Pełny tekst do pobrania w serwisie zewnętrznym

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

    Pełny tekst do pobrania w portalu

  • Mixed graph edge coloring

    Publikacja

    - DISCRETE MATHEMATICS - Rok 2009

    W pracy rozważany jest problem kolorowania krawędzi grafu mieszanego, tj. grafu zawierającego zawiero skierowane, jak i nieskierowane krawędzie. Motywację do badań stanowią zagadnienia komunikacyjne z zakresu szeregowania zadań.

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Non-disjoint Decomposition Using r-admissibility and Graph Coloring and Its Application in Index Generation Functions Minimization

    Publikacja

    - Rok 2019

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Interval vertex-coloring of a graph with forbidden colors

    Publikacja

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Interval Vertex-Coloring of a Graph With Forbidden Colors

    Publikacja

    - Rok 1989

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Interval edge coloring of a graph with forbidden colors

    Publikacja

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Kolorowanie grafów z ograniczeniami na liczbę wierzchołków w określonym kolorze = Graph coloring model with restrictions on cardinalities of vertexes in particular color

    Publikacja

    - Rok 2012

    W artykule rozważamy problem takiego kolorowania grafów, w którym klasy kolorów mają ograniczoną z góry moc. Zagadnie to znajduje ciekawe zastosowania praktyczne i jest naturalnym uogólnieniem problemu kolorowania grafów. W artykule ustalamy złożoność obliczeniową dla grafów pełnych $r$-dzielnych i dla kilku innych prostych klas grafów oraz dla problemu dwukolorowania.

  • 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 serwisie zewnętrznym

  • 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

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

  • 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

  • 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

  • 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

  • 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

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

  • 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

  • Marek Kubale prof. dr hab. inż.

     Details concerning: Qualifications, Experiences, Editorial boards, Ph.D. theses supervised, Books, and Recent articles can be found at http://eti.pg.edu.pl/katedra-algorytmow-i-modelowania-systemow/Marek_KubaleGoogle ScholarSylwetka prof. Marka Kubalego Prof. Marek Kubale pracuje na Wydziale ETI Politechniki Gdańskiej nieprzerwanie od roku 1969. W tym czasie napisał ponad 150 prac naukowych, w tym ponad 40 z listy JCR. Ponadto...

  • 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 serwisie zewnętrznym

  • Dataset of non-isomorphic graphs of the coloring types (K4,K4;n), 1<n<R(4,4)

    Dane Badawcze
    open access

    For K4 graph, a coloring type (K4,K4;n) is such an edge coloring of the full Kn graph, which does not have the K4 subgraph in the first color (representing by no edges in the graph) or the K4 subgraph in the second color (representing by edges in the graph).The Ramsey number R(4,4) is the smallest natural number n such that for any edge coloring of...

  • 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

  • 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

  • Dataset of non-isomorphic graphs of the coloring types (K3,Km-e;n), 2<m<7, 1<n<R(K3,Km-e).

    Dane Badawcze
    open access

    For K3 and Km-e graphs, a coloring type (K3,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K3 subgraph in the first color (representing by no edges in the graph) or the Km-e subgraph in the second color (representing by edges in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K3,Km-e)...

  • Dataset of non-isomorphic graphs of the coloring types (K3,Km;n), 2<m<7, 1<n<R(3,m)

    Dane Badawcze
    open access

    For K3 and Km graphs, a coloring type (K3,Km;n) is such an edge coloring of the full Kn graph, which does not have the K3 subgraph in the first color (representing by no edges in the graph) or the Km subgraph in the second color (representing by edges in the graph).The Ramsey number R(3,m) is the smallest natural number n such that for any edge coloring...

  • Dataset of non-isomorphic graphs of the coloring types (Km,K3-e;n), 4<m<8, 1<n<R(Km,K3-e)

    Dane Badawcze
    open access

    For Km and K3-e graphs, a coloring type (Km,K3-e;n) is such an edge coloring of the full Kn graph, which does not have the Km subgraph in the first color (representing by no edges in the graph) or the K3-e subgraph in the second color (representing by edges in the graph). K3-e means the full Km graph with one edge removed.The Ramsey number R(Km,K3-e)...

  • Dataset of non-isomorphic graphs being coloring types (K6-e,Km-e;n), 2<m<5, 1<n<R(K6-e,Km-e)

    Dane Badawcze
    open access

    For K6-e and Km-e graphs, the type coloring (K6-e,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K6-e subgraph in the first color (no edge in the graph) or the Km-e subgraph in the second color (exists edge in the graph). Km-e means the full Km graph with one edge removed. The Ramsey number R(K6-e,Km-e) is the smallest...

  • Dataset of non-isomorphic graphs of the coloring types (K4,Km-e;n), 2<m<5, 1<n<R(K4,Km-e)

    Dane Badawcze
    open access

    For K4 and Km-e graphs, a coloring type (K4,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K4 subgraph in the first color (representing by no edges in the graph) or the Km-e subgraph in the second color (representing by edges in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K4,Km-e)...

  • Dataset of non-isomorphic graphs being coloring types (K3-e,Km-e;n), 2<m<8, 1<n<R(K3-e,Km-e)

    Dane Badawcze
    open access

    For K3-e and Km-e graphs, the type coloring (K3-e,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K3-e subgraph in the first color (no edge in the graph) or the Km-e subgraph in the second color (exists edge in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K3-e,Km-e) is the smallest...

  • Dataset of non-isomorphic graphs being coloring types (K4-e,Km-e;n), 2<m<7, 1<n<R(K4-e,Km-e)

    Dane Badawcze
    open access

    For K4-e and Km-e graphs, the type coloring (K4-e,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K4-e subgraph in the first color (no edge in the graph) or the Km-e subgraph in the second color (exists edge in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K4-e,Km-e) is the smallest...

  • 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&gt;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&gt;n/3, and it is polynomially solvable if s, n/3.

    Pełny tekst do pobrania w portalu

  • 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

  • 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 serwisie zewnętrznym

  • 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

  • Dataset of non-isomorphic graphs being coloring types (K5-e,Km-e;n), 2<m<5, 1<n<R(K5-e,Km-e)

    Dane Badawcze
    open access

    For K5-e and Km-e graphs, the type coloring (K5-e,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K5-e subgraph in the first color (no edge in the graph) or the Km-e subgraph in the second color (exists edge in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K5-e,Km-e) is the smallest...

  • 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

  • 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) -&gt; N+ such that |c(u)-c(v)| &gt;= 2 for each edge uv \in E(H) and |c(u)-c(v)| &gt;= 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

  • 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

  • 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 λ&gt;=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

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

  • 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

  • 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

  • Sprawiedliwe i półsprawiedliwe pokolorowania grafów kubicznych

    Publikacja

    - Rok 2014

    W pracy rozpatrywane są sprawiedliwe i półsprawiedliwe pokolorowania grafów kubicznych. Pokazano, że w odróżnieniu od tego pierwszego, który jest łatwy, problem istnienia pokolorowań półsprawiedliwych jest NP-zupełny w szerokim zakresie parametrów grafów.

  • 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

  • Linear game non-contextuality and Bell inequalities—a graph-theoretic approach

    Publikacja

    - NEW JOURNAL OF PHYSICS - Rok 2016

    We study the classical and quantum values of a class of one-and two-party unique games, that generalizes the well-known XOR games to the case of non-binary outcomes. In the bipartite case the generalized XOR(XOR-d) games we study are a subclass of the well-known linear games. We introduce a 'constraint graph' associated to such a game, with the constraints defining the game represented by an edge-coloring of the graph. We use the...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • 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

  • 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

  • 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

  • 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

  • New potential functions for greedy independence and coloring

    Publikacja

    - DISCRETE APPLIED MATHEMATICS - Rok 2015

    A potential function $f_G$ of a finite, simple and undirected graph $G=(V,E)$ is an arbitrary function $f_G : V(G) \rightarrow \mathbb{N}_0$ that assigns a nonnegative integer to every vertex of a graph $G$. In this paper we define the iterative process of computing the step potential function $q_G$ such that $q_G(v)\leq d_G(v)$ for all $v\in V(G)$. We use this function in the development of new Caro-Wei-type and Brooks-type...

    Pełny tekst do pobrania w portalu

  • A note on mixed tree coloring

    Publikacja

    - INFORMATION PROCESSING LETTERS - Rok 2008

    Zaproponowano liniowy algorytm dla problemu kolorowania mieszanego w drzewach, uzyskując tym samym poprawę w stosunku do algorytmu o złożoności O(n^2) podanego w pracy [P. Hansen, J. Kuplinsky, D. de Werra, Mixed graph colorings, Math. Methods Oper. Res. 45 (1997) 145-160].

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Edge coloring of graphs of signed class 1 and 2

    Publikacja

    - DISCRETE APPLIED MATHEMATICS - Rok 2023

    Recently, Behr (2020) introduced a notion of the chromatic index of signed graphs and proved that for every signed graph (G, σ) it holds that ∆(G) ≤ χ′(G,σ) ≤ ∆(G) + 1, where ∆(G) is the maximum degree of G and χ′ denotes its chromatic index. In general, the chromatic index of (G, σ) depends on both the underlying graph G and the signature σ. In the paper we study graphs G for which χ′(G, σ) does not depend on σ. To this aim we...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Optimal edge-coloring with edge rate constraints

    Publikacja

    - NETWORKS - Rok 2013

    We consider the problem of covering the edges of a graph by a sequence of matchings subject to the constraint that each edge e appears in at least a given fraction r(e) of the matchings. Although it can be determined in polynomial time whether such a sequence of matchings exists or not [Grötschel et al., Combinatorica (1981), 169–197], we show that several questions about the length of the sequence are computationally intractable....

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Clonal selection in discrete optimization

    Publikacja

    - Rok 2009

    W rozprawie zajmujemy się efektywnymi metodami przybliżonego rozwiązywania problemów optymalizacji dyskretnej, a w szczególności algorytmami opartymi na metodzie selekcji klonalnej (SK), należącymi do kategorii sztucznych systemów immunologicznych. Techniki optymalizacji to znaczące pole badań w informatyce, a niektóre ze starszych technik, takie jak algorytmy genetyczne, symulowane wyżarzanie czy przeszukiwanie tabu, stały się...

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

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

  • Joanna Raczek dr inż.

    Wykształcenie 1997 -- 2001 Studia inżynierskie, Wydział Fizyki Technicznej i Matematyki Stosowanej, Politechnika Gdańska. Kierunek: Matematyka, specjalność: Matematyka Stosowana. 2001 -- 2003 Studia magisterskie, Wydział Fizyki Technicznej i Matematyki Stosowanej, Politechnika Gdańska. Kierunek: Matematyka, specjalność: Matematyka Stosowana. 2000 -- 2004 Studia inżynierskie, Wydział Elektroniki, Informatyki i Telekomunikacji,...

  • Graph models of clos networks

    Publikacja

    - Rok 2007

    ...

  • Graph classes generated by Mycielskians

    Publikacja

    - Discussiones Mathematicae Graph Theory - Rok 2020

    In this paper we use the classical notion of weak Mycielskian M'(G) of a graph G and the following sequence: M'_{0}(G) =G, M'_{1}(G)=M'(G), and M'_{n}(G)=M'(M'_{n−1}(G)), to show that if G is a complete graph oforder p, then the above sequence is a generator of the class of p-colorable graphs. Similarly, using Mycielskian M(G) we show that analogously defined sequence is a generator of the class consisting of graphs for which the...

    Pełny tekst do pobrania w portalu