A constant time algorithm for some optimization problems in rotagraphs and fasciagraphs

作者：Bouznif M; Moncel J; Preissmann M^*

来源：Discrete Applied Mathematics, 2016, 208: 27-40.

DOI：10.1016/j.dam.2016.63.009

• Combinatorial optimization problems
• Constant-time algorithm
• Grids
• Fasciagraphs
• Rotagraphs
• Min-Plus algebra

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.

• 出版日期2016-7-31