Robust algorithms for restricted domains

DOI10.1016/S0196-6774(03)00048-8zbMath1079.68110OpenAlexW4241342922MaRDI QIDQ4458875

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-hardRobustnessefficient algorithmsUnit disk graphsWell-covered graphs

Mathematics Subject Classification ID

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

Related Items (19)

Approximating 2-cliques in unit disk graphs ⋮ Structural parameterizations with modulator oblivion ⋮ Homothetic polygons and beyond: maximal cliques in intersection graphs ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Co-bipartite neighborhood edge elimination orderings ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ A weakly robust PTAS for minimum clique partition in unit disk graphs ⋮ Unnamed Item ⋮ On the chromatic number of random geometric graphs ⋮ Improper colouring of (random) unit disk graphs ⋮ Location-oblivious distributed unit disk graph coloring ⋮ Approximating minimum independent dominating sets in wireless networks ⋮ Improper coloring of unit disk graphs ⋮ The number of disk graphs ⋮ Unnamed Item ⋮ Coloring Artemis graphs ⋮ Mind the independence gap ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure ⋮ Unnamed Item

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