An exact algorithm for the channel ass assignment problem

KRÁĽ, Daniel. An exact algorithm for the channel ass assignment problem. Discrete Applied Mathematics. AMSTERDAM: Elsevier B.V., 2005, roč. 145, č. 2, s. 326-331. ISSN 0166-218X. Dostupné z: https://doi.org/10.1016/j.dam.2004.01.020.

Základní údaje

Originální název

An exact algorithm for the channel ass assignment problem

Autoři

KRÁĽ, Daniel

Vydání

Discrete Applied Mathematics, AMSTERDAM, Elsevier B.V. 2005, 0166-218X

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.585

DOI

https://doi.org/10.1016/j.dam.2004.01.020

UT WoS

000226452700017

---

Anotace

V originále

A channel assignment problem is a triple (V, E, w) where V is a vertex set, E is an edge set and w is a function assigning edges positive integer weights. An assignment c of integers between 1 and K to the vertices is proper if c(u) - c(v) greater than or equal to w(uv) for each uv is an element of E; the smallest K for which there is a proper assignment is called the span. The input problem is set to be l-bounded if the values of w do not exceed l. We present an algorithm running in time O(n(l + 2)(n)) which outputs the span for l-bounded channel assignment problems with n vertices. An algorithm running in time O(nl(l + 2)(n)) for computing the number of different proper assignments of span at most K is further presented. (C) 2004 Elsevier B.V. All rights reserved.