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

Algorithmsefficient algorithmsNP-hardRobustnessUnit disk graphsWell-covered graphs

Mathematics Subject Classification ID

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

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

(24)

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

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)