Back to Search
Start Over
A constant time algorithm for some optimization problems in rotagraphs and fasciagraphs.
- Source :
-
Discrete Applied Mathematics . Jul2016, Vol. 208, p27-40. 14p. - Publication Year :
- 2016
-
Abstract
- This paper deals with optimization problems on rotagraphs and fasciagraphs. These graphs are repetitive structures that generalize grids and toroidal grids, respectively. We develop a theoretical framework and get linear-time and constant-time generic algorithms for wide classes of combinatorial problems which are defined in a purely combinatorial way. These classes of problems include in particular many classical optimization problems that are NP-complete in general. Our results unify in a single framework many results of the literature, in particular on the topic of domination–and its variants–in grids. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 208
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 115366338
- Full Text :
- https://doi.org/10.1016/j.dam.2016.03.009