The cyclic cutwidth of trees

DOI10.1016/S0166-218X(98)00098-5MaRDI QIDQ1270769zbMATH OpenOpenAlexFDO

Authors K. Appert

Publication date 3 November 1998

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

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

cyclic cutwidthembeddinglinear cutwidthtree

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Review text

For an embedding of a graph \(G\) in another graph \(H\), the cutwidth of the embedding is the maximum number of edges of \(G\) along an edge of the host graph. The (linear) cutwidth of a graph is the minimum cutwidth of an embedding in a path; the cyclic cutwidth of a graph is the minimum cutwidth of an embedding in a cycle. In this paper, it is shown that the cyclic cutwidth of a tree equals its linear cutwidth.

Recommendations

• The cyclic wirelength of trees
• scientific article; zbMATH DE number 1490011
• Cyclic cutwidths of the two-dimensional ordinary and cylindrical meshes
• Characterizations of \(k\)-cutwidth critical trees
• scientific article; zbMATH DE number 1854105

Cites work

• scientific article; zbMATH DE number 4070955 (Why is no real title available?)
• Optimal Assignments of Numbers to Vertices
• The congestion of \(n\)-cube layout on a rectangular grid
• Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees

Cited in

(28)

• Exact wirelength of hypercubes on a grid
• On spanning tree congestion
• The cyclic wirelength of trees
• Embedding hypercubes and folded hypercubes onto Cartesian product of certain trees
• Wirelength of hypercubes into certain trees
• Minimal congestion trees
• Cyclic cutwidths of the two-dimensional ordinary and cylindrical meshes
• Wirelength of \(1\)-fault Hamiltonian graphs into wheels and fans
• A linear time algorithm for embedding hypercube into cylinder and torus
• Multistart search for the cyclic cutwidth minimization problem
• Embedding of hypercubes into sibling trees
• Embedding of recursive circulants into certain necklace graphs
• A rigorous proof on circular wirelength for hypercubes
• Maximum incomplete recursive circulants in graph embeddings
• Embeddings of circulant networks
• Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength
• Embedding of hypercubes into necklace, windmill and snake graphs
• scientific article; zbMATH DE number 1490011 (Why is no real title available?)
• scientific article; zbMATH DE number 1760009 (Why is no real title available?)
• scientific article; zbMATH DE number 1854105 (Why is no real title available?)
• Bothway embedding of circulant network into grid
• Cutwidth of iterated caterpillars
• Embedding Wheel - like Networks
• Minimum average congestion of enhanced and augmented hypercubes into complete binary trees
• Embedding augmented cube into certain trees and windmill graphs
• An upper bound for edge congestion and the exact wirelength of embedding onto BC graphs
• Multiplicity of finite graphs over the real line
• Cut trees in the topological analysis of branching patterns

This page was built for publication: The cyclic cutwidth of trees

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