Skip to Main content Skip to Navigation
Reports

Circuit visiting 10 ordered vertices in infinite grids

David Coudert 1 Frédéric Giroire 1 Ignasi Sau Valls 1, 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : A circuit in a simple undirected graph G=(V,E) is a sequence of vertices {v_1,v_2,...,v_{k+1}} such that v_1=v_{k+1} and {v_i,v_{i+1}} \in E for i=1,...,k. A circuit C is said to be edge-simple if no edge of G is used twice in C. In this article we study the following problem: which is the largest integer k such that, given any subset of k ordered vertices of an infinite square grid, there exists an edge-simple circuit visiting the k vertices in the prescribed order? We prove that k=10. To this end, we first provide a counterexample implying that k<11. To show that k>=10, we introduce a methodology, based on the notion of core graph, to reduce drastically the number of possible vertex configurations, and then we test each one of the resulting configurations with an ILP solver.
Document type :
Reports
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/inria-00378586
Contributor : David Coudert <>
Submitted on : Friday, April 24, 2009 - 5:25:57 PM
Last modification on : Tuesday, June 22, 2021 - 8:14:03 PM
Long-term archiving on: : Friday, October 12, 2012 - 5:16:07 PM

File

RR-6910.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00378586, version 1

Citation

David Coudert, Frédéric Giroire, Ignasi Sau Valls. Circuit visiting 10 ordered vertices in infinite grids. [Research Report] RR-6910, INRIA. 2009. ⟨inria-00378586⟩

Share

Metrics

Record views

638

Files downloads

175