On distance constrained labeling of disk graphs

DOI10.1016/J.TCS.2004.06.026zbMATH Open1071.68083OpenAlexW2158249986WikidataQ60488774 ScholiaQ60488774MaRDI QIDQ703553FDOQ703553

Authors: 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

Recommendations

• scientific article; zbMATH DE number 1877050
• \( L ( 2 , 1 )\)-labeling of disk intersection graphs
• A new characterization of disk graphs and its application.
• Approximation and Online Algorithms
• Online coloring and \(L(2,1)\)-labeling of unit disk intersection graphs

zbMATH Keywords

ApproximationDisk graphLabelingOnline

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

• A tight bound for online colouring of disk graphs
• An 8-approximation algorithm for \(L(2 ,1)\)-labeling of unit disk graphs
• On the \(L(p,1)\)-labelling of graphs
• Title not available (Why is that?)
• Online coloring of disk graphs
• New results on radio \(k\)-labelings of distance graphs
• Note on coloring of double disk graphs
• \( L ( 2 , 1 )\)-labeling of disk intersection graphs
• Online coloring and \(L(2,1)\)-labeling of unit disk intersection graphs
• Approximation and Online Algorithms

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q703553)