Carregant...
Carregant...

Vés al contingut (premeu Retorn)

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

Autor
Diaz, J.; Kaminski, M.; Thilikos, D.
Tipus d'activitat
Article en revista
Revista
Discrete mathematics
Data de publicació
2010-02
Volum
310
Número
3
Pàgina inicial
531
Pàgina final
536
DOI
https://doi.org/10.1016/j.disc.2009.03.046 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/7471 Obrir en finestra nova
URL
http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V00-4W5M0F6-1&_user=1517299&_rdoc=1&_fmt=&_orig=search&_sort=d&_docanchor=&view=c&_acct=C000053450&_version=1&_urlVersion=0&_userid=1517299&md5=1e2bef9d894d917638c79c05b0770d49 Obrir en finestra nova
Resum
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.
Citació
Díaz, J.; Kaminski, M.; Thilikos, D. A note on the subgraphs of the (2×\infty)-grid. "Discrete mathematics", Febrer 2010, vol. 310, núm. 3, p. 531-536.
Paraules clau
Partial Grids Linear-time Algorithm Biconnected Components
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants