Robust algorithms for restricted domains

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

Jeremy P. Spinrad, Vijay Raghavan

Publication date: 14 March 2004

Published in: Journal of Algorithms (Search for Journal in Brave)

zbMATH Keywords

Algorithms; NP-hard; Robustness; efficient algorithms; Unit disk graphs; Well-covered graphs

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Unnamed Item, Location-oblivious distributed unit disk graph coloring, On the chromatic number of random geometric graphs, Approximating minimum independent dominating sets in wireless networks, Coloring Artemis graphs, Homothetic polygons and beyond: maximal cliques in intersection graphs, Co-bipartite neighborhood edge elimination orderings, 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, Large Induced Subgraphs via Triangulations and CMSO, Improper coloring of unit disk graphs