Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
From MaRDI portal
Publication:4441902
DOI10.1137/S0097539702431840zbMath1069.68120OpenAlexW2112505974MaRDI QIDQ4441902
Guy Even, Dana Ron, Zvi Lotker, Shakhar Smorodinsky
Publication date: 8 January 2004
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539702431840
Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Combinatorial complexity of geometric structures (52C45)
Related Items (82)
Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs ⋮ Dynamic conflict-free colorings in the plane ⋮ On Conflict-Free Multi-coloring ⋮ Opposite-quadrant depth in the plane ⋮ Conflict-Free Colourings of Uniform Hypergraphs With Few Edges ⋮ Unsplittable coverings in the plane ⋮ Coloring Axis-Parallel Rectangles ⋮ Maximum value of conflict-free vertex-connection number of graphs ⋮ Conflict-Free Coloring of Graphs ⋮ Conflict-Free Coloring of Intersection Graphs ⋮ Conflict-free coloring bounds on open neighborhoods ⋮ Structural parameterization for minimum conflict-free colouring ⋮ A tight bound for conflict-free coloring in terms of distance to cluster ⋮ Coloring planar homothets and three-dimensional hypergraphs ⋮ Colorings with neighborhood parity condition ⋮ Decomposition of multiple coverings into more parts ⋮ 1-planar graphs are odd 13-colorable ⋮ On conflict-free proper colourings of graphs without small degree vertices ⋮ Conflict‐free chromatic number versus conflict‐free chromatic index ⋮ Dushnik-Miller dimension of TD-Delaunay complexes ⋮ Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics ⋮ Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth ⋮ On odd colorings of planar graphs ⋮ A short note on conflict‐free coloring on closed neighborhoods of bounded degree graphs ⋮ Conflict-free connection number of random graphs ⋮ An algebraic formulation of hypergraph colorings ⋮ An improvement of the bound on the odd chromatic number of 1-planar graphs ⋮ Conflict free colorings of (strongly) almost disjoint set-systems ⋮ A note on the conflict-free chromatic index ⋮ Coloring lines and Delaunay graphs with respect to boxes ⋮ Unique-maximum coloring of plane graphs ⋮ Graph unique-maximum and conflict-free colorings ⋮ Polynomial Time Algorithms for Bichromatic Problems ⋮ Conflict-free coloring of intersection graphs of geometric objects ⋮ Coloring intersection hypergraphs of pseudo-disks ⋮ Conflict-free coloring for rectangle ranges using \(O(n ^{.382})\) colors ⋮ Coloring half-planes and bottomless rectangles ⋮ Conflict-free coloring of points on a line with respect to a set of intervals ⋮ A Short Note on Open-Neighborhood Conflict-Free Colorings of Graphs ⋮ Many disjoint edges in topological graphs ⋮ On conflict-free connection of graphs ⋮ Maximizing and minimizing the number of generalized colorings of trees ⋮ Colorful strips ⋮ Complexity of conflict-free colorings of graphs ⋮ Strong conflict-free coloring for intervals ⋮ Conflict-Free Colourings of Graphs and Hypergraphs ⋮ On variants of conflict-free-coloring for hypergraphs ⋮ Many disjoint edges in topological graphs ⋮ Graphs with conflict-free connection number two ⋮ Conflict-Free Colouring of Graphs ⋮ Exact and Fixed Parameter Tractable Algorithms for Max-Conflict-Free Coloring in Hypergraphs ⋮ Online Conflict-Free Colouring for Hypergraphs ⋮ Conflict-free (vertex)-connection numbers of graphs with small diameters ⋮ Conflict-free coloring of string graphs ⋮ Coloring axis-parallel rectangles ⋮ Dynamic Offline Conflict-Free Coloring for Unit Disks ⋮ CONFLICT-FREE COLORINGS OF SHALLOW DISCS ⋮ Parameterized algorithms for conflict-free colorings of graphs ⋮ Delaunay graphs of point sets in the plane with respect to axis‐parallel rectangles ⋮ (Strong) conflict-free connectivity: algorithm and complexity ⋮ Strong conflict-free connection of graphs ⋮ INFINITE COMBINATORICS PLAIN AND SIMPLE ⋮ Brooks type results for conflict-free colorings and \(\{a, b \}\)-factors in graphs ⋮ Parameterized Complexity of Conflict-Free Graph Coloring ⋮ Hitting sets online and unique-MAX coloring ⋮ Conflict-free connection of trees ⋮ Non-monochromatic and conflict-free colorings on tree spaces and planar network spaces ⋮ Convex partial transversals of planar regions ⋮ Combinatorial optimization in system configuration design ⋮ Conflict-free coloring of unit disks ⋮ Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points ⋮ Unnamed Item ⋮ 2-colorability of \(r\)-uniform hypergraphs ⋮ Ordered Coloring Grids and Related Graphs ⋮ Hasse diagrams with large chromatic number ⋮ Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods ⋮ Remarks on proper conflict-free colorings of graphs ⋮ Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points. ⋮ Dynamic Conflict-Free Colorings in the Plane ⋮ Some results on strong conflict-free connection number of graphs ⋮ Coloring intersection hypergraphs of pseudo-disks ⋮ Conflict-free coloring: graphs of bounded clique width and intersection graphs
Uses Software
This page was built for publication: Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
