Minimum-Density Identifying Codes in Square Grids

DOI10.1007/978-3-319-41168-2_7MaRDI QIDQ2830060zbMATH OpenOpenAlexFDO

Authors Frédéric Havet, M. Bouznif, Myriam Preissmann

Publication date 9 November 2016

Published in Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01346750/file/AAIM-grid-code.pdf

zbMATH Keywords

discharging methodidentifying codesquare grid

Mathematics Subject Classification ID

Distance in graphs (05C12) Density (toughness, etc.) (05C42) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Exact Minimum Density of Codes Identifying Vertices in the Square Grid
• Minimum density of identifying codes of king grids
• Minimum density of identifying codes of king grids
• On Identifying Codes in the Triangular and Square Grids
• On the density of identifying codes in the square lattice
• New lower bound for 2-identifying code in the square grid
• The number of completely different optimal identifying codes in the infinite square grid
• New bounds on the minimum density of an identifying code for the infinite hexagonal grid
• Lower bounds for identifying codes in some infinite grids
• An optimal strongly identifying code in the infinite triangular grid

Cites work

• A family of optimal identifying codes in \(\mathbb Z^2\)
• Exact Minimum Density of Codes Identifying Vertices in the Square Grid
• Fault-tolerant locating-dominating sets
• General bounds for identifying codes in some infinite regular graphs
• Identifying codes in some subgraphs of the square lattice
• New bounds for codes identifying vertices in graphs
• New bounds on the minimum density of an identifying code for the infinite hexagonal grid
• New lower bound for 2-identifying code in the square grid
• On a new class of codes for identifying vertices in graphs
• Optimal lower bound for 2-identifying codes in the hexagonal grid

Cited in

(18)

• New bounds for codes identifying vertices in graphs
• Periodicity of identifying codes in strips
• Operads of finite posets
• On the minimum size of an identifying code over all orientations of a graph
• Optimal identifying codes of two families of Cayley graphs
• The number of completely different optimal identifying codes in the infinite square grid
• New lower bound for 2-identifying code in the square grid
• Locating-domination and identification
• Optimal lower bound for 2-identifying codes in the hexagonal grid
• On Identifying Codes in the Triangular and Square Grids
• Identifying codes for infinite triangular grids with a finite number of rows
• Exact Minimum Density of Codes Identifying Vertices in the Square Grid
• Minimum density of identifying codes of king grids
• Minimum density of identifying codes of king grids
• Identifying codes in some subgraphs of the square lattice
• Density of identifying codes of hexagonal grids with finite number of rows
• On the density of (1, )-locating-dominating codes in the infinite square grid
• An optimal strongly identifying code in the infinite triangular grid

Describes a project that uses

Uses Software

• IDonSquareGridR2

This page was built for publication: Minimum-Density Identifying Codes in Square Grids

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