Generic algorithms for some decision problems on fasciagraphs and rotagraphs

DOI10.1016/J.DISC.2012.02.013MaRDI QIDQ442402zbMATH OpenOpenAlexFDO

Authors M. Bouznif, Myriam Preissmann, Julien Moncel

Publication date 10 August 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2012.02.013

zbMATH Keywords

algorithmic complexitycombinatorial optimizationfasciagraphsgridsNP-hard problemsrotagraphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Algebraic approach to fasciagraphs and rotagraphs
• Computing graph invariants on rotagraphs using dynamic algorithm approach: The case of (2, 1)-colorings and independence numbers
• A constant time algorithm for some optimization problems in rotagraphs and fasciagraphs
• scientific article; zbMATH DE number 1390094
• scientific article; zbMATH DE number 3845609

Cites work

• \(L(2,1)\)-labeling of direct product of paths and cycles
• 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
• Critical cyclic patterns related to the domination number of the torus
• Distance-related invariants on polygraphs
• Generic algorithms for some decision problems on fasciagraphs and rotagraphs
• Graphs, dioids and semirings. New models and algorithms.
• scientific article; zbMATH DE number 3845609 (Why is no real title available?)
• scientific article; zbMATH DE number 4147519 (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?)
• Identifying codes in some subgraphs of the square lattice

Cited in

(6)

• Distance-related invariants on polygraphs
• Algebraic approach to fasciagraphs and rotagraphs
• Optimal locating-total dominating sets in strips of height 3
• \(L(2, 1)\)-labeling of the Cartesian and strong product of two directed cycles
• A constant time algorithm for some optimization problems in rotagraphs and fasciagraphs
• Generic algorithms for some decision problems on fasciagraphs and rotagraphs

This page was built for publication: Generic algorithms for some decision problems on fasciagraphs and rotagraphs

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