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)

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

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)