A note on the subgraphs of the (2×\infty)-grid

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/7471

Title:	A note on the subgraphs of the (2×\infty)-grid
Author:	Díaz Cort, Josep; Kaminski, Marcin; Thilikos Touloupas, Dimitrios
Other authors:	Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
Abstract:	We give a linear-time algorithm checking whether a graph is a subgraph of the (2×k)-grid for some value of k. Our algorithm is based on a detailed characterization of the structure of such graphs.
Subject(s):	-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat -Graph algorithms -Partial grids Linear-time algorithm Biconnected components -Algorismes -- Informàtica
Rights:	Attribution-NonCommercial-NoDerivs 3.0 Spain http://creativecommons.org/licenses/by-nc-nd/3.0/es/
Document type:	Article - Published version Article
Share: