Robust algorithms for restricted domains

DOI10.1016/S0196-6774(03)00048-8zbMATH Open1079.68110OpenAlexW4241342922MaRDI QIDQ4458875FDOQ4458875

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

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

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)

Cited In (22)

• Title not available (Why is that?)
• Location-oblivious distributed unit disk graph coloring
• Improper colouring of (random) unit disk graphs
• Treewidth versus clique number. II: Tree-independence number
• Title not available (Why is that?)
• Improper coloring of unit disk graphs
• A weakly robust PTAS for minimum clique partition in unit disk graphs
• Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
• 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
• Approximating 2-cliques in unit disk graphs
• Mind the independence gap
• Approximating minimum independent dominating sets in wireless networks
• The number of disk graphs
• Co-bipartite neighborhood edge elimination orderings
• Large Induced Subgraphs via Triangulations and CMSO
• Title not available (Why is that?)
• Robust algorithms for restricted domains
• 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)