Channel assignment and weighted coloring

DOI<link itemprop=identifier href="https://doi.org/10.1002/1097-0037(200009)36:2<114::AID-NET6>3.0.CO;2-G" /><114::AID-NET6>3.0.CO;2-G 10.1002/1097-0037(200009)36:2<114::AID-NET6>3.0.CO;2-GzbMath0971.90100OpenAlexW2082873662MaRDI QIDQ4519133

Bruce A. Reed, Colin J. H. McDiarmid

Publication date: 3 December 2000

Full work available at URL: https://doi.org/10.1002/1097-0037(200009)36:2<114::aid-net6>3.0.co;2-g

zbMATH Keywords

approximation algorithmtriangular latticehexagonal cellsweighted coloringradio channel assignmentcellular communication system

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (37)

1-local 7/5-competitive Algorithm for Multicoloring Hexagonal Graphs ⋮ Online Multi-Coloring with Advice ⋮ Greedy online frequency allocation in cellular networks ⋮ Every triangle-free induced subgraph of the triangular lattice is \((5m,2m)\)-choosable ⋮ A constant-competitive algorithm for online OVSF code assignment ⋮ On \(L(k, k - 1, \ldots, 1)\) labeling of triangular lattice ⋮ 2-local 5/4-competitive algorithm for multicoloring triangle-free hexagonal graphs ⋮ Better bounds for incremental frequency allocation in bipartite graphs ⋮ 1-local 7/5-competitive algorithm for multicoloring hexagonal graphs ⋮ Tight Lower Bounds for the Complexity of Multicoloring ⋮ A linear time algorithm for \(7\)-\([3\)coloring triangle-free hexagonal graphs] ⋮ Simpler multicoloring of triangle-free hexagonal graphs ⋮ A Constant-Competitive Algorithm for Online OVSF Code Assignment ⋮ A 1-local 4/3-competitive algorithm for multicoloring a subclass of hexagonal graphs ⋮ 2-local 7/6-competitive algorithm for multicolouring a sub-class of hexagonal graphs ⋮ On irreducible no‐hole L(2, 1)‐coloring of trees ⋮ Improper coloring of unit disk graphs ⋮ Approximation algorithms for channel assignment with constraints ⋮ IMPROPER COLORING OF WEIGHTED GRID AND HEXAGONAL GRAPHS ⋮ Absolute and asymptotic bounds for online frequency allocation in cellular networks ⋮ A class of weakly perfect graphs ⋮ Online coloring a token graph ⋮ Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs ⋮ Three Results on Frequency Assignment in Linear Cellular Networks ⋮ Online call control in cellular networks revisited ⋮ Homomorphisms of hexagonal graphs to odd cycles ⋮ Worst-case analysis of a dynamic channel assignment strategy ⋮ A 1-local asymptotic 13/9-competitive algorithm for multicoloring hexagonal graphs ⋮ Three results on frequency assignment in linear cellular networks ⋮ Perfectness and imperfectness of unit disk graphs on triangular lattice points ⋮ A technique for multicoloring triangle-free hexagonal graphs ⋮ Graph imperfection. I ⋮ On the properties of weighted minimum colouring games ⋮ Improper Colourings of Unit Disk Graphs ⋮ 2-local distributed algorithms for generalized coloring of hexagonal graphs ⋮ Online multi-coloring with advice ⋮ On algorithms for (\(P_5\), gem)-free graphs

Cites Work

• Geometric algorithms and combinatorial optimization
• Some simplified NP-complete graph problems
• Graph coloring bounds for cellular radio
• The channel assignment problem for mutually adjacent sites
• Graph labeling and radio channel assignment

This page was built for publication: Channel assignment and weighted coloring