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

Consultar RECERCAT

Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/7471

Título:	A note on the subgraphs of the (2×\infty)-grid
Autor/a:	Díaz Cort, Josep; Kaminski, Marcin; Thilikos Touloupas, Dimitrios
Otros autores:	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.
Materia(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
Derechos:	Attribution-NonCommercial-NoDerivs 3.0 Spain http://creativecommons.org/licenses/by-nc-nd/3.0/es/
Tipo de documento:	Artículo - Versión publicada Artículo
Compartir: