Identifying codes in some subgraphs of the square lattice

DOI10.1016/j.tcs.2004.02.007zbMath1047.94019OpenAlexW1977247825MaRDI QIDQ596073

Julien Moncel, Sylvain Gravier, Marc Daniel

Publication date: 10 August 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.02.007

zbMATH Keywords

graph theoryidentifying codesfasciagraphs

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial codes (94B25)

Related Items (13)

A constant time algorithm for some optimization problems in rotagraphs and fasciagraphs ⋮ Identifying codes in the complementary prism of cycles ⋮ Optimal identifying codes of two families of Cayley graphs ⋮ Periodicity of identifying codes in strips ⋮ Generic algorithms for some decision problems on fasciagraphs and rotagraphs ⋮ Identifying codes of cycles with odd orders ⋮ Identifying codes for infinite triangular grids with a finite number of rows ⋮ Identifying codes of cycles ⋮ Minimum density of identifying codes of king grids ⋮ Liar's domination ⋮ Minimum density of identifying codes of king grids ⋮ Locating-Domination and Identification ⋮ Minimum-Density Identifying Codes in Square Grids

Cites Work

• Unnamed Item
• Unnamed Item
• A generalization of the pentomino exclusion problem: dislocation of graphs
• The matching polynomial of a polygraph
• Linear and combinatorial optimization in ordered algebraic structures
• New bounds for codes identifying vertices in graphs
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• Algebraic approach to fasciagraphs and rotagraphs
• On a new class of codes for identifying vertices in graphs
• Identifying codes with small radius in some infinite regular graphs

This page was built for publication: Identifying codes in some subgraphs of the square lattice