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

DOI10.1016/J.DAM.2016.03.009zbMATH Open1337.05098OpenAlexW2342558999MaRDI QIDQ284833FDOQ284833

Authors M. Bouznif, Myriam Preissmann, Julien Moncel

Publication date 18 May 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2016.03.009

zbMATH Keywords

grids\(\min\)-plus algebracombinatorial optimization problemsconstant-time algorithmfasciagraphsrotagraphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27)

Recommendations

• Algebraic approach to fasciagraphs and rotagraphs
• scientific article; zbMATH DE number 1990832
• Generic algorithms for some decision problems on fasciagraphs and rotagraphs
• scientific article; zbMATH DE number 1390094
• Polynomial time analysis of toroidal periodic graphs

Cites work

• scientific article; zbMATH DE number 4039319 (Why is no real title available?)
• scientific article; zbMATH DE number 2099356 (Why is no real title available?)
• scientific article; zbMATH DE number 842019 (Why is no real title available?)
• scientific article; zbMATH DE number 1390094 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• A generalization of the pentomino exclusion problem: dislocation of graphs
• Algebraic approach to fasciagraphs and rotagraphs
• Computing graph invariants on rotagraphs using dynamic algorithm approach: The case of (2, 1)-colorings and independence numbers
• Computing the domination number of grid graphs
• Critical cyclic patterns related to the domination number of the torus
• Distance-related invariants on polygraphs
• Easy problems for tree-decomposable graphs
• Exact values for three domination-like problems in circular and infinite grid graphs of small height
• Generalized matrix period in max-plus algebra
• Generic algorithms for some decision problems on fasciagraphs and rotagraphs
• Graph structure and monadic second-order logic. A language-theoretic approach
• Graphs, dioids and semirings. New models and algorithms.
• Identifying codes in some subgraphs of the square lattice
• Locating-total domination in graphs
• Matrix period in max-algebra
• Roman domination number of the Cartesian products of paths and cycles
• \(L(2,1)\)-labeling of direct product of paths and cycles

Cited in

(1)

• Generic algorithms for some decision problems on fasciagraphs and rotagraphs

This page was built for publication: A constant time algorithm for some optimization problems in rotagraphs and fasciagraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q284833)