Approximation algorithms on consistent dynamic map labeling

DOI10.1016/J.TCS.2016.06.006MaRDI QIDQ2629235zbMATH OpenOpenAlexWikidataFDO

Authors Chung-Shou Liao, Chih-Wei Liang, Sheung-Hung Poon

Publication date 5 July 2016

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

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

zbMATH Keywords

approximation algorithmNP-completenessdynamic map labelingactive range optimization

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• Approximation Algorithms on Consistent Dynamic Map Labeling
• Optimizing active ranges for consistent dynamic map labeling
• Consistent labeling of rotating maps
• A unified model and algorithms for temporal map labeling
• Consistent labeling of rotating maps

Cites work

• scientific article; zbMATH DE number 6472588 (Why is no real title available?)
• A note on maximum independent sets in rectangle intersection graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• Computational geometry. Algorithms and applications.
• Efficient approximation algorithms for tiling and packing problems with rectangles
• Fundamentals of Computation Theory
• Label placement by maximum independent set in rectangles
• Maximum independent set of rectangles
• Optimizing active ranges for consistent dynamic map labeling
• Polynomial-time approximation schemes for packing and piercing fat objects
• The Problem of Compatible Representatives

Cited in

(17)

• An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling
• Minimum point-overlap labelling*
• A unified model and algorithms for temporal map labeling
• Adaptive labeling algorithms for the dynamic assignment problem
• Optimizing active ranges for consistent dynamic map labeling
• Minimum point-overlap labeling
• Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract)
• Approximation Algorithms on Consistent Dynamic Map Labeling
• scientific article; zbMATH DE number 1629978 (Why is no real title available?)
• Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs
• Placing labels in road maps: algorithms and complexity
• scientific article; zbMATH DE number 7651158 (Why is no real title available?)
• Trajectory-based dynamic map labeling
• Consistent dynamic map labeling with fairness and importance
• Solving dynamic labeling problems to optimality using solution space reductions
• Dynamic Point Labeling is Strongly PSPACE-Complete
• scientific article; zbMATH DE number 1057929 (Why is no real title available?)

This page was built for publication: Approximation algorithms on consistent dynamic map labeling

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