On the treewidth of toroidal grids

DOI10.1016/J.DAM.2015.06.027MaRDI QIDQ897618zbMATH OpenOpenAlexFDO

Authors Masashi Kiyomi, Yoshio Okamoto, Yota Otachi

Publication date 7 December 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2015.06.027

zbMATH Keywords

treewidthtoroidal gridbramble

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12)

Recommendations

• Treewidth and gonality of glued grid graphs
• Parameters tied to treewidth
• Lower bounds on the pathwidth of some grid-like graphs
• Treewidth lower bounds with brambles
• Computational aspects of treewidth for graph

Cites work

• scientific article; zbMATH DE number 4121424 (Why is no real title available?)
• A partial k-arboretum of graphs with bounded treewidth
• Achievable sets, brambles, and sparse treewidth obstructions
• Graph minors. II. Algorithmic aspects of tree-width
• Graph searching and a min-max theorem for tree-width
• Lower bounds for treewidth of product graphs
• Lower bounds on the pathwidth of some grid-like graphs
• Quickly excluding a planar graph
• The carving-width of generalized hypercubes
• The vertex separation number of a graph equals its path-width
• Treewidth of Cartesian products of highly connected graphs

Cited in

(6)

• Lower bounds on the pathwidth of some grid-like graphs
• Parameters tied to treewidth
• The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration
• On resource placements in 3D tori.
• Treewidth of grid subsets
• Treewidth and gonality of glued grid graphs

This page was built for publication: On the treewidth of toroidal grids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897618)