Robust algorithms for restricted domains

DOI10.1016/S0196-6774(03)00048-8MaRDI QIDQ4458875zbMATH OpenOpenAlexFDO

Authors Vijay Raghavan, Jeremy P. Spinrad

Publication date 14 March 2004

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0196-6774(03)00048-8

zbMATH Keywords

AlgorithmsNP-hardefficient algorithmsRobustnessUnit disk graphsWell-covered graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Robust algorithms for restricted domains
• scientific article; zbMATH DE number 3883614
• Robust algorithms: a different approach to oracles
• Robust algorithms for the stable set problem
• scientific article; zbMATH DE number 6321164
• Constrained robustness analysis by randomized algorithms
• Algorithms for stable and perturbation-resilient problems
• scientific article; zbMATH DE number 1489831
• Dynamic algorithms for recoverable robustness problems

Cited in

(22)

• Location-oblivious distributed unit disk graph coloring
• Improper colouring of (random) unit disk graphs
• Treewidth versus clique number. II: Tree-independence number
• Improper coloring of unit disk graphs
• A weakly robust PTAS for minimum clique partition in unit disk graphs
• QPTAS and subexponential algorithm for maximum clique on disk graphs
• Robust algorithms: a different approach to oracles
• Coloring Artemis graphs
• Solving problems on special classes of graphs
• Homothetic polygons and beyond: maximal cliques in intersection graphs
• Structural parameterizations with modulator oblivion
• Structural parameterizations with modulator oblivion
• Approximating 2-cliques in unit disk graphs
• Mind the independence gap
• Approximating minimum independent dominating sets in wireless networks
• Treewidth versus clique number. I: Graph classes with a forbidden structure
• The number of disk graphs
• Co-bipartite neighborhood edge elimination orderings
• Large Induced Subgraphs via Triangulations and CMSO
• Robust algorithms for restricted domains
• scientific article; zbMATH DE number 7053376 (Why is no real title available?)
• On the chromatic number of random geometric graphs

This page was built for publication: Robust algorithms for restricted domains

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