Edge-Simple Circuits Through 10 Ordered Vertices in Square Grids

David Coudert 1, * Frédéric Giroire 1 Ignasi Sau 1, 2
* Auteur correspondant
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , 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 {v1 , v2 , . . . , vk+1 } such that v1 = vk+1 and {vi , vi+i } ∈ 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.
Type de document :
Communication dans un congrès
International Workshop on Combinatorial Algorithms -- IWOCA, Jun 2009, Hradec nad Moravicì, Czech Republic. Springer, 5874, 2009, Lecture Notes in Computer Science
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00429146
Contributeur : David Coudert <>
Soumis le : samedi 31 octobre 2009 - 15:12:59
Dernière modification le : lundi 4 décembre 2017 - 15:14:09
Document(s) archivé(s) le : mardi 16 octobre 2012 - 13:01:48

Fichier

CGS09_IWOCA_nostyle.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00429146, version 1

Collections

Citation

David Coudert, Frédéric Giroire, Ignasi Sau. Edge-Simple Circuits Through 10 Ordered Vertices in Square Grids. International Workshop on Combinatorial Algorithms -- IWOCA, Jun 2009, Hradec nad Moravicì, Czech Republic. Springer, 5874, 2009, Lecture Notes in Computer Science. 〈inria-00429146〉

Partager

Métriques

Consultations de la notice

247

Téléchargements de fichiers

112