On distance constrained labeling of disk graphs

DOI10.1016/j.tcs.2004.06.026zbMath1071.68083OpenAlexW2158249986WikidataQ60488774 ScholiaQ60488774MaRDI QIDQ703553

Jiří Fiala, Aleksei V. Fishkin, Fedor V. Fomin

Publication date: 11 January 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.06.026

zbMATH Keywords

ApproximationDisk graphLabelingOnline

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

A tight bound for online colouring of disk graphs ⋮ New results on radio \(k\)-labelings of distance graphs ⋮ Online Coloring and $L(2,1)$-Labeling of Unit Disk Intersection Graphs ⋮ An 8-approximation algorithm for \(L(2 ,1)\)-labeling of unit disk graphs ⋮ Note on coloring of double disk graphs ⋮ On the \(L(p,1)\)-labelling of graphs ⋮ \( L ( 2 , 1 )\)-labeling of disk intersection graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unit disk graphs
• Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems
• Unit disk graph recognition is NP-hard
• On-line coloring of geometric intersection graphs
• A bound on the chromatic number of the square of a planar graph
• On-line and first fit colorings of graphs
• Labelling Graphs with a Condition at Distance 2
• Graph labeling and radio channel assignment
• Optimal approximation of sparse hessians and its equivalence to a graph coloring problem
• Partial covers of graphs
• The $L(2,1)$-Labeling Problem on Graphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Representing graphs by disks and balls (a survey of recognition-complexity results)

This page was built for publication: On distance constrained labeling of disk graphs