Robust algorithms for restricted domains

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

Jeremy P. Spinrad, Vijay Raghavan

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)

Cited In (20)

• 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
• 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?)
• On the chromatic number of random geometric graphs

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Robust algorithms: a different approach to oracles 👍 👎
• Dynamic algorithms for recoverable robustness problems 👍 👎
• Robust algorithms for restricted domains 👍 👎
• Robust algorithms for the stable set problem 👍 👎
• Constrained robustness analysis by randomized algorithms 👍 👎
• Algorithms for stable and perturbation-resilient problems 👍 👎

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)