Cluttered orderings for the complete bipartite graph
Cluttered orderings for the complete bipartite graph
复制标题
DOI：
10.1016/j.dam.2005.06.005
复制
发表时间：
2005-11
期刊：
影响因子：
--
通讯作者：
Meinard Müller;T. Adachi;Masakazu Jimbo
中科院分区：
文献类型：
--
作者：
Meinard Müller;T. Adachi;Masakazu Jimbo
为了最小化大型磁盘阵列（RAID）中的访问代价，Cohen，Colbourn和Froncek在一系列论文中引入并研究了各种集合系统的（d，f）-杂乱序的概念，d，f∈N。在图的情况下，这相当于边集的排序，使得任何d个连续边中包含的点的数量以数量f为界。对于完全图，Cohen等人给出了小参数d的最优解，并介绍了基于包裹Δ-标号的一般构造原理。本文研究了完全二部图的杂乱序。我们将包裹Δ-标记的概念适用于二分情况，并引入子图的（d，f）-运动的概念。由此我们得到了一个关于杂乱序的一般存在定理。本文的主要结果是明确地构造了几个无限族的包裹Δ-标号，导致相应的二部图的混乱的顺序。
To minimize the access cost in large disk arrays (RAID) Cohen, Colbourn, and Froncek introduced and investigated in a series of papers the concept of (d,f)-cluttered orderings of various set systems, d,f∈N. In case of a graph this amounts to an ordering of the edge set such that the number of points contained in any d consecutive edges is bounded by the number f. For the complete graph, Cohen et al. gave some optimal solution for small parameters d and introduced some general construction principle based on wrapped Δ-labellings. In this paper, we investigate cluttered orderings for the complete bipartite graph. We adapt the concept of a wrapped Δ-labelling to the bipartite case and introduce the notion of a (d,f)-movement for subgraphs. From this we get a general existence theorem for cluttered orderings. The main result of this paper is the explicit construction of several infinite families of wrapped Δ-labellings leading to cluttered orderings for the corresponding bipartite graphs.