On distance constrained labeling of disk graphs

DOI10.1016/J.TCS.2004.06.026MaRDI QIDQ703553zbMATHOpenAlexWikidataFDO

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

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)

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

Cites work

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

Cited in

(10)

• New results on radio \(k\)-labelings of distance graphs
• scientific article; zbMATH DE number 1877050 (Why is no real title available?)
• \( L ( 2 , 1 )\)-labeling of disk intersection graphs
• A tight bound for online colouring of disk graphs
• On the \(L(p,1)\)-labelling of graphs
• Online coloring and \(L(2,1)\)-labeling of unit disk intersection graphs
• Online coloring of disk graphs
• An 8-approximation algorithm for \(L(2 ,1)\)-labeling of unit disk graphs
• Note on coloring of double disk 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)