A note on the subgraphs of the <textbox>(2×∞)</textbox>-grid

设为首页

收藏本站

网站地图 | English | 公务邮箱

About the library

Background
History
Leadership
Organization

Readers' Guide

Opening Hours
Collections
Help Via Email

Publications

Electronic Information Resources

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

详细信息查看全文

作者：Josep Dí ; az ; Marcin Kamiń ; ski ; Dimitrios M. Thilikos
关键词：Partial grids ; Linear-time algorithm ; Biconnected components
刊名：Discrete Mathematics
出版年：2010
出版时间：6 February 2010
年：2010
卷：310
期：3
页码：531-536
全文大小：507 K

文摘

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.