scientific article; zbMATH DE number 7651158

DOI10.4230/LIPICS.ESA.2020.19MaRDI QIDQ5874486zbMATH OpenFDO

Authors Sujoy Bhore, Guangping Li, Martin Nöllenburg

Publication date 7 February 2023

Full work available at URL https://arxiv.org/abs/2002.07611

zbMATH Keywords

approximation algorithmsindependent setsrectangle intersection graphsdynamic algorithmsexperimental evaluation

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Approximation algorithms on consistent dynamic map labeling
• Approximation Algorithms on Consistent Dynamic Map Labeling
• A Lagrangean decomposition for the maximum independent set problem applied to map labeling
• scientific article; zbMATH DE number 1696627
• Approximation algorithms for independent sets in map graphs
• An efficient and effective approximation algorithm for the Map Labeling Problem
• scientific article; zbMATH DE number 1629978
• A dynamic survey of graph labeling
• New approximation algorithms for map labeling with sliding labels

Cites work

• scientific article; zbMATH DE number 6850309 (Why is no real title available?)
• scientific article; zbMATH DE number 1368469 (Why is no real title available?)
• A deamortization approach for dynamic spanner and dynamic maximal matching
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation schemes for covering and packing problems in image processing and VLSI
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Consistent labeling of rotating maps
• Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time
• Dynamic algorithms for monotonic interval scheduling problem
• Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles
• Dynamic fractional cascading
• Dynamic orthogonal range searching on the RAM, revisited
• Dynamic set cover: improved algorithms and lower bounds
• Efficient algorithms for interval graphs and circular-arc graphs
• Finding a Maximum Clique in an Arbitrary Graph
• Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
• Fully dynamic maximal independent set with sublinear update time
• Independent sets in vertex-arrival streams
• Label placement by maximum independent set in rectangles
• Maximum independent set of rectangles
• Optimal packing and covering in the plane are NP-complete
• Optimizing active ranges for consistent dynamic map labeling
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Reducibility among combinatorial problems
• The maximum clique problem

Cited in

(4)

• An Algorithmic Study of Fully Dynamic Independent Sets for Map Labeling
• Robust online algorithms for dynamic choosing problems
• Approximation Algorithms on Consistent Dynamic Map Labeling
• Consistent dynamic map labeling with fairness and importance

Describes a project that uses

Uses Software

• LEDA

This page was built for publication:

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