Greedy algorithms for generalized k-rankings of paths

A k-ranking of a graph is a labeling of the vertices with positive integers 1,2,…,k so that every path connecting two vertices with the same label contains a vertex of larger label. An optimal ranking is one in which k is minimized. Let Pn be a path with n vertices. A greedy algorithm can be used to successively label each vertex with the smallest possible label that preserves the ranking property. We seek to show that when a greedy algorithm is used to label the vertices successively from left to right, we obtain an optimal ranking. A greedy algorithm of this type was given by Bodlaender et al. in 1998 [1] which generates an optimal k-ranking of Pn. In this paper we investigate two generalizations of rankings. We first consider bounded (k,s)-rankings in which the number of times a label can be used is bounded by a predetermined integer s. We then consider kt-rankings where any path connecting two vertices with the same label contains t vertices with larger labels. We show for both generalizations that when G is a path, the analogous greedy algorithms generate optimal k-rankings. We then proceed to quantify the minimum number of labels that can be used in these rankings. We define the bounded rank number to be the smallest number of labels that can be used in a (k,s)-ranking and show for n?2, where i=⌊log₂(s)⌋+1. We define the kt-rank number, to be the smallest number of labels that can be used in a kt-ranking. We present a recursive formula that gives the kt-rank numbers for paths, showing for all an−1<j?an where {an} is defined as follows: a₁=1 and an=⌊((t+1)/t)an−1⌋+1.     

Scheduling Constraints and Interference Graph Properties for Graph-based Interference Coordination in Cellular OFDMA Networks

The currently emerging 802.16e (WiMAX) and 3GPP Long Term Evolution (LTE) cellular systems are based on Orthogonal Frequency Division Multiple Access (OFDMA). OFDMA suffers from heavy inter-cell interference if neighboring base stations use the same frequency range. One approach to solve this issue is the application of beamforming antennas in combination with interference coordination (IFCO) mechanisms between base stations. In this paper, we trace the problem of IFCO back to the graph coloring problem and investigate the achievable resource utilization of the interference coordinated system. We develop a heuristic that allows the combination of arbitrary scheduling algorithms with the IFCO mechanism. This allows an efficient utilization of the radio system’s frequency resources while still obeying scheduling constraints, such as Quality of Service requirements. Finally, we study the tradeoff between fairness and the total system throughput.

Edge coloring of bipartite graphs with constraints

A classical result from graph theory states that the edges of an l-regular bipartite graph can be colored using exactly l colors so that edges that share an endpoint are assigned different colors. In this paper, we study two constrained versions of the bipartite edge coloring problem.

Full-size image

磺化丙酮-甲醛缩聚物的结构表征及其发色机理分析

采用对磺化丙酮-甲醛缩聚物的结构进行了表征,含有羰基、羟基、碳碳双键等基团。通过紫外光谱和碘量法发现,不饱和键被NaBH4还原,使SAF减水剂的吸光度降低。SAF减水剂的棕红色是由于含有较长的双键或共轭羰基链段和助色基团-SO3所致。     

光纤着色工序常见问题的处理

在实际光纤着色工序中,经常会遇到着色偏心、颜色偏淡、固化不良,着色后光纤衰减偏大、断纤等质量问题。对上述这些经常发生的质量问题进行了详细的分析和探讨,旨在提供一种能够快速解决问题的思路,确保高效率生产。     

一种基于图论的RFID防冲突建模与优化方法

针对RFID系统的超高频段、多读写器的静态拓扑结构,研究了读写器冲突问题,并提出了一种图论的图着色算法与遗传算法相结合的防冲突干扰方法.该静态预定义算法对读写器冲突建立图论模型,将读写器时隙分配问题转化为图论模型的K-顶点着色问题,优化遗传算法并用于求解图的K-顶点着色问题,求得最小时隙数和最优时隙分配方案.最后将算法应用于算例.实验结果表明该方法可行、实用,能够有效地防止读写器冲突干扰.     

Research of RFID anti collision algorithm based on

针对射频识别技术（R．FID）存在多个阅读器同时传输数据容易产生冲突的问题,提出了一种基于图染色理论的防止冲突的算法。该算法利用图的染色算法将可能存在冲突的阅读器染成不同的颜色,使得每种不相同的颜色不能同时获得相同的时隙,降低了多个阅读器同时传输数据产生冲突的可能性。分析表明：采用该算法明显地降低了阅读器之间的冲突率,同时得到最小的时隙数,提高了信道利用率,为R-FID防冲突算法提供了一种新的解决方案,同时为基于TDMA的广播调度模式也提供了一种新的时隙分配方式。     

添加剂铬酸钾对TC4钛合金微弧氧化膜层性能的影响

以TC4钛合金为基体,在硅酸钠电解液中进行微弧氧化(MAO)。电解液的主要成分为Na2SiO3、Na3PO4和NaOH,工艺条件为:电压450V,频率500Hz,占空比30%,时间5min。通过向电解液中添加0.5g/LK2CrO4对微弧氧化膜层进行着色。采用涡流测厚仪、维氏硬度计、扫描电镜、X射线荧光光谱分析仪以及中性盐雾试验等,研究了K2CrO4添加剂对膜层厚度、显微硬度和形貌等性能的影响。结果表明,所得微弧氧化膜层为典型的不规则多孔氧化物陶瓷膜层,显微硬度和耐蚀性明显优于基材。在电解液中加入K2CrO4后,MAO膜层由灰色转变为深黄色;K2CrO4使膜层粗糙度和孔径增大,与基体结合处的缺陷减少,结合力增强;膜层的脆性和内应力降低,耐蚀性增强。     

肉类色泽变化机理研究进展

影响肉颜色的因素很多,主要包括肉自身和外界因素(如动物的遗传基因、宰前和宰后因素、肌肉的基本化学组成以及产品的加工、包装、运输、储藏、销售、食用的前处理等)。本文对近几十年来肉类化学、鲜肉成色机理的研究、影响肉色稳定性的化学因素和生物学因素、主要的肉色评价方法进行了综述。国内外专家对有关肉色的相关性指标和影响肉色的因素均存在很大的争议,但已被大家广泛认可的是:肌红蛋白的绝对含量和肌红蛋白的三种不同形式的相对含量是肉色稳定性的基础。     

着色剂及其在肉制品中的应用

本文论述了着色剂的种类、发展趋势,及其在肉制品中的使用原则和检测方法。