D 2015

The Min-max Edge q-Coloring Problem

LARJOMAA, Tommi and Alexandru POPA

Basic information

Original name

The Min-max Edge q-Coloring Problem

Authors

LARJOMAA, Tommi (246 Finland) and Alexandru POPA (642 Romania, belonging to the institution)

Edition

Duluth, MN, USA, 25th International Workshop, IWOCA 2014, LNCS 8986, p. 226-237, 12 pp. 2015

Publisher

Springer

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Switzerland

Confidentiality degree

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

Publication form

printed version "print"

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/15:00087418

Organization unit

Faculty of Informatics

ISBN

978-3-319-19314-4

ISSN

DOI

UT WoS

000365044500020

Keywords in English

Algorithms; Color; Combinatorial mathematics; Graph theory; MESH networking; Polynomial approximation; Trees (mathematics)

Tags

Změněno: 6/5/2016 04:41, RNDr. Pavel Šmerk, Ph.D.

Abstract

V originále

In this paper we introduce and study a new problem named min-max edge q -coloring which is motivated by applications in wireless mesh networks. The input of the problem consists of an undirected graph and an integer q. The goal is to color the edges of the graph with as many colors as possible such that: (a) any vertex is incident to at most q different colors, and (b) the maximum size of a color group (i.e. set of edges identically colored) is minimized. We show the following results: 1. Min-max edge q-coloring is NP-hard, for any q>=2. 2. A polynomial time exact algorithm for min-max edge q-coloring on trees. 3. Exact formulas of the optimal solution for cliques. 4. An approximation algorithm for planar graphs.