scientific article; zbMATH DE number 1507300
From MaRDI portal
Publication:4504025
zbMath0955.05100MaRDI QIDQ4504025
Publication date: 13 February 2001
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (22)
Reverse shortest path problem for unit-disk graphs ⋮ Linear-Time Approximation Algorithms for Unit Disk Graphs ⋮ Faster approximation for maximum independent set on unit disk graph ⋮ Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs ⋮ Efficient independent set approximation in unit disk graphs ⋮ The homogeneous broadcast problem in narrow and wide strips. I: Algorithms ⋮ Establishing herd immunity is hard even in simple geometric networks ⋮ An optimal algorithm for \(L_1\) shortest paths in unit-disk graphs ⋮ Approximate strong separation with application in fractional graph coloring and preemptive scheduling. ⋮ Unnamed Item ⋮ Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs ⋮ Near-optimal algorithms for shortest paths in weighted unit-disk graphs ⋮ Approximation algorithms for maximum independent set of a unit disk graph ⋮ The within-strip discrete unit disk cover problem ⋮ An approximation algorithm for the general max-min resource sharing problem ⋮ Improved Algorithm for Maximum Independent Set on Unit Disk Graph ⋮ The number of disk graphs ⋮ Local edge colouring of Yao-like subgraphs of unit disk graphs ⋮ Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs. ⋮ A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation ⋮ Unnamed Item ⋮ Perfectness and imperfectness of unit disk graphs on triangular lattice points
This page was built for publication: