The min-max edge q-coloring problem

Tommi Larjomaa, Alexandru Popa

    Research output: Contribution to journalArticle

    3 Citations (Scopus)

    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: Min-max edge q-coloring is NP-hard, for any q ≥ 2. A polynomial time exact algorithm for min-max edge q-coloring on trees. Exact formulas of the optimal solution for cliques and almost tight bounds for bicliques and hypergraphs. A non-trivial lower bound of the optimal solution with respect to the average degree of the graph. An approximation algorithm for planar graphs.

    Original languageEnglish
    Pages (from-to)505-528
    Number of pages24
    JournalJournal of Graph Algorithms and Applications
    Volume19
    Issue number1
    DOIs
    Publication statusPublished - Aug 1 2015

    Fingerprint

    Coloring
    Min-max
    Colouring
    Color
    Optimal Solution
    Bicliques
    Q-integers
    Wireless Mesh Networks
    Wireless mesh networks (WMN)
    Approximation algorithms
    Exact Algorithms
    Graph in graph theory
    Hypergraph
    Clique
    Undirected Graph
    Planar graph
    Polynomial-time Algorithm
    Approximation Algorithms
    NP-complete problem
    Polynomials

    ASJC Scopus subject areas

    • Computer Science(all)
    • Computer Science Applications
    • Geometry and Topology
    • Theoretical Computer Science
    • Computational Theory and Mathematics

    Cite this

    The min-max edge q-coloring problem. / Larjomaa, Tommi; Popa, Alexandru.

    In: Journal of Graph Algorithms and Applications, Vol. 19, No. 1, 01.08.2015, p. 505-528.

    Research output: Contribution to journalArticle

    Larjomaa, Tommi ; Popa, Alexandru. / The min-max edge q-coloring problem. In: Journal of Graph Algorithms and Applications. 2015 ; Vol. 19, No. 1. pp. 505-528.
    @article{b58b3b70010a4cffa866f0f35019dc08,
    title = "The min-max edge q-coloring problem",
    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: Min-max edge q-coloring is NP-hard, for any q ≥ 2. A polynomial time exact algorithm for min-max edge q-coloring on trees. Exact formulas of the optimal solution for cliques and almost tight bounds for bicliques and hypergraphs. A non-trivial lower bound of the optimal solution with respect to the average degree of the graph. An approximation algorithm for planar graphs.",
    author = "Tommi Larjomaa and Alexandru Popa",
    year = "2015",
    month = "8",
    day = "1",
    doi = "10.7155/jgaa.00373",
    language = "English",
    volume = "19",
    pages = "505--528",
    journal = "Journal of Graph Algorithms and Applications",
    issn = "1526-1719",
    publisher = "Brown University",
    number = "1",

    }

    TY - JOUR

    T1 - The min-max edge q-coloring problem

    AU - Larjomaa, Tommi

    AU - Popa, Alexandru

    PY - 2015/8/1

    Y1 - 2015/8/1

    N2 - 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: Min-max edge q-coloring is NP-hard, for any q ≥ 2. A polynomial time exact algorithm for min-max edge q-coloring on trees. Exact formulas of the optimal solution for cliques and almost tight bounds for bicliques and hypergraphs. A non-trivial lower bound of the optimal solution with respect to the average degree of the graph. An approximation algorithm for planar graphs.

    AB - 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: Min-max edge q-coloring is NP-hard, for any q ≥ 2. A polynomial time exact algorithm for min-max edge q-coloring on trees. Exact formulas of the optimal solution for cliques and almost tight bounds for bicliques and hypergraphs. A non-trivial lower bound of the optimal solution with respect to the average degree of the graph. An approximation algorithm for planar graphs.

    UR - http://www.scopus.com/inward/record.url?scp=84951292325&partnerID=8YFLogxK

    UR - http://www.scopus.com/inward/citedby.url?scp=84951292325&partnerID=8YFLogxK

    U2 - 10.7155/jgaa.00373

    DO - 10.7155/jgaa.00373

    M3 - Article

    AN - SCOPUS:84951292325

    VL - 19

    SP - 505

    EP - 528

    JO - Journal of Graph Algorithms and Applications

    JF - Journal of Graph Algorithms and Applications

    SN - 1526-1719

    IS - 1

    ER -