# Wyniki wyszukiwania dla: backbone coloring - MOST Wiedzy

## Wyszukiwarka

Wyniki wyszukiwania dla: backbone coloring
• wyników na stronę:

wszystkich: 8

### Wyniki wyszukiwania dla: backbone coloring

• #### The Backbone Coloring Problem for Bipartite Backbones

Publikacja

- Rok 2015

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

• #### The Backbone Coloring Problem for Small Graphs

Publikacja

- Rok 2014

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

• #### Optimal backbone coloring of split graphs with matching backbones

Publikacja

- Rok 2015

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

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

Publikacja

- Rok 2015

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

Publikacja

- Rok 2012

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

Publikacja

- Rok 2015

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

• #### A note on fast approximate backbone coloring of split graphs with star--like backbones

Publikacja

Dla grafu G = (V, E) z wyróżnionym podgrafem H, kolorowanie szkieletowe jest zdefiniowane jako odwzorowanie c spełniające |c(u) - c(v)| &gt; 1 dla każdej krawędzi z E(H) oraz |c(u) - c(v)| &gt; 0 dla każdej krawędzi z E(G). W pracy przedstawiono 1-przybliżony algorytm kolorowania szkieletowego split grafów ze skojarzeniem w szkielecie o złożoności O(|V|) oraz 1-przybliżony algorytm dla split grafów z rozłącznymi gwiazdami w szkielecie.

Pełny tekst do pobrania w serwisie zewnętrznym

Publikacja

- Rok 2012