LARJOMAA, Tommi and Alexandru POPA. The Min-max Edge q-Coloring Problem. In 25th International Workshop, IWOCA 2014, LNCS 8986. Duluth, MN, USA: Springer, 2015, p. 226-237. ISBN 978-3-319-19314-4. Available from: https://dx.doi.org/10.1007/978-3-319-19315-1_20.
Other formats:   BibTeX LaTeX RIS
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
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Switzerland
Confidentiality degree is not subject to a state or trade secret
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 0302-9743
Doi http://dx.doi.org/10.1007/978-3-319-19315-1_20
UT WoS 000365044500020
Keywords in English Algorithms; Color; Combinatorial mathematics; Graph theory; MESH networking; Polynomial approximation; Trees (mathematics)
Tags firank_B
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 6/5/2016 04:41.
Abstract
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.
PrintDisplayed: 26/4/2024 06:19