期刊文献+
共找到20篇文章
< 1 >
每页显示 20 50 100
New mixed broadcast scheduling approach using neural networks and graph coloring in wireless sensor network 被引量:5
1
作者 Zhang Xizheng Wang Yaonan 《Journal of Systems Engineering and Electronics》 SCIE EI CSCD 2009年第1期185-191,共7页
Due to the mutual interference and sharing of wireless links in TDMA wireless sensor networks, conflicts will occur when data messages are transmitting between nodes. The broadcast scheduling problem (BSP) is aimed ... Due to the mutual interference and sharing of wireless links in TDMA wireless sensor networks, conflicts will occur when data messages are transmitting between nodes. The broadcast scheduling problem (BSP) is aimed to schedule each node in different slot of fixed length frame at least once, and the objective of BSP is to seek for the optimal feasible solution, which has the shortest length of frame slots, as well as the maximum node transmission. A two-stage mixed algorithm based on a fuzzy Hopfield neural network is proposed to solve this BSP in wireless sensor network. In the first stage, a modified sequential vertex coloring algorithm is adopted to obtain a minimal TDMA frame length. In the second stage, the fuzzy Hopfleld network is utilized to maximize the channel utilization ratio. Experimental results, obtained from the running on three benchmark graphs, show that the algorithm can achieve better performance with shorter frame length and higher channel utilizing ratio than other exiting BSP solutions. 展开更多
关键词 wireless sensor network broadcast scheduling fuzzy Hopfield network graph coloring.
下载PDF
Network evolution driven by dynamics applied to graph coloring
2
作者 吴建设 李力光 +2 位作者 王晓华 于昕 焦李成 《Chinese Physics B》 SCIE EI CAS CSCD 2013年第6期262-267,共6页
An evolutionary network driven by dynamics is studied and applied to the graph coloring problem. From an initial structure, both the topology and the coupling weights evolve according to the dynamics. On the other han... An evolutionary network driven by dynamics is studied and applied to the graph coloring problem. From an initial structure, both the topology and the coupling weights evolve according to the dynamics. On the other hand, the dynamics of the network are determined by the topology and the coupling weights, so an interesting structure-dynamics co-evolutionary scheme appears. By providing two evolutionary strategies, a network described by the complement of a graph will evolve into several clusters of nodes according to their dynamics. The nodes in each cluster can be assigned the same color and nodes in different clusters assigned different colors. In this way, a co-evolution phenomenon is applied to the graph coloring problem. The proposed scheme is tested on several benchmark graphs for graph coloring. 展开更多
关键词 network dynamics evolution of network evolutionary strategies graph coloring problem
下载PDF
On the Maximum Number of Dominating Classes in Graph Coloring
3
作者 Bing Zhou 《Open Journal of Discrete Mathematics》 2016年第2期70-73,共4页
We investigate the dominating-c-color number,, of a graph G. That is the maximum number of color classes that are also dominating when G is colored using colors. We show that where is the join of G and . This result a... We investigate the dominating-c-color number,, of a graph G. That is the maximum number of color classes that are also dominating when G is colored using colors. We show that where is the join of G and . This result allows us to construct classes of graphs such that and thus provide some information regarding two questions raised in [1] and [2]. 展开更多
关键词 graph coloring Dominating Sets Dominating coloring Classes Chromatic Number Dominating Color Number
下载PDF
Uniquely Tree Colorable Graphs
4
作者 Deng Ping Department of Applied Mathematics, Southwest Jiaotong University, Chengdu 610031, China 《Journal of Modern Transportation》 1997年第1期90-95,共6页
In this paper, the concepts of tree chromatic numbers and uniquely tree colorable graphs are introduced. After discussion some fundamental properties, three necessary conditions for a simple graph to be uniquely tr... In this paper, the concepts of tree chromatic numbers and uniquely tree colorable graphs are introduced. After discussion some fundamental properties, three necessary conditions for a simple graph to be uniquely tree colorable are given. Moreover, a series of uniquely tree colorable graphs are constructed. 展开更多
关键词 tree chromatic number tree partition uniquely tree colorable graph
下载PDF
An Intelligent Prediction Model for Target Protein Identification in Hepatic Carcinoma Using Novel Graph Theory and ANN Model
5
作者 G.Naveen Sundar Stalin Selvaraj +4 位作者 D.Narmadha K.Martin Sagayam A.Amir Anton Jone Ayman A.Aly Dac-Nhuong Le 《Computer Modeling in Engineering & Sciences》 SCIE EI 2022年第10期31-46,共16页
Hepatocellular carcinoma(HCC)is one major cause of cancer-related mortality around the world.However,at advanced stages of HCC,systematic treatment options are currently limited.As a result,new pharmacological targets... Hepatocellular carcinoma(HCC)is one major cause of cancer-related mortality around the world.However,at advanced stages of HCC,systematic treatment options are currently limited.As a result,new pharmacological targetsmust be discovered regularly,and then tailored medicines against HCC must be developed.In this research,we used biomarkers of HCC to collect the protein interaction network related to HCC.Initially,DC(Degree Centrality)was employed to assess the importance of each protein.Then an improved Graph Coloring algorithm was used to rank the target proteins according to the interaction with the primary target protein after assessing the top ranked proteins related to HCC.Finally,physio-chemical proteins are used to evaluate the outcome of the top ranked proteins.The proposed graph theory and machine learning techniques have been compared with six existing methods.In the proposed approach,16 proteins have been identified as potential therapeutic drug targets for Hepatic Carcinoma.It is observable that the proposed method gives remarkable performance than the existing centrality measures in terms of Accuracy,Precision,Recall,Sensitivity,Specificity and F-measure. 展开更多
关键词 Drug target detection hepatic carcinoma degree centrality graph coloring artificial neural network model
下载PDF
Independent Cycle Time Assignment for Min-max Systems
6
作者 Wen-De Chen Yue-Gang Tao Hong-Nian Yu 《International Journal of Automation and computing》 EI 2010年第2期254-260,共7页
A variety of problems in digital circuits, computer networks, automated manufacturing plants, etc., can be modeled as min-max systems. The cycle time is an important performance metric of such systems. In this paper, ... A variety of problems in digital circuits, computer networks, automated manufacturing plants, etc., can be modeled as min-max systems. The cycle time is an important performance metric of such systems. In this paper, we focus on the cycle time assignment of minimax systems which corresponds to the pole assignment problem in traditional linear control systems. For the min- max system with max-plus inputs and outputs, we show that the cycle time can be assigned disjointedly by a state feedback, if and only if the system is reachable. Furthermore, a necessary and sufficient condition for the cycle time to be assigned independently by a state feedback is given. The methods are constructive, and some numerical examples are given to illustrate how the methods work in practice. 展开更多
关键词 Cycle time coloring graph independent assignment min-max systems state feedback.
下载PDF
Robust graph coloring based on the matrix semi-tensor product with application to examination timetabling 被引量:9
7
作者 Meirong XU Yuzhen WANG Airong WEI 《Control Theory and Technology》 EI CSCD 2014年第2期187-197,共11页
This paper investigates the robust graph coloring problem with application to a kind of examination timetabling by using the matrix semi-tensor product, and presents a number of new results and algorithms. First, usin... This paper investigates the robust graph coloring problem with application to a kind of examination timetabling by using the matrix semi-tensor product, and presents a number of new results and algorithms. First, using the matrix semi-tensor product, the robust graph coloring is expressed into a kind of optimization problem taking in an algebraic form of matrices, based on which an algorithm is designed to find all the most robust coloring schemes for any simple graph. Second, an equivalent problem of robust graph coloring is studied, and a necessary and sufficient condition is proposed, from which a new algorithm to find all the most robust coloring schemes is established. Third, a kind of examination timetabling is discussed by using the obtained results, and a method to design a practicable timetabling scheme is presented. Finally, the effectiveness of the results/algorithms presented in this paper is shown by two illustrative examples. 展开更多
关键词 Robust graph coloring ALGORITHM Examination timetabling Semi-tensor product
原文传递
A novel nest-based scheduling method for mobile wireless body area networks 被引量:2
8
作者 Zhijun Xie Guangyan Huang +3 位作者 Roozbeh Zarei Zhenyan Ji Hongwu Ye Jing He 《Digital Communications and Networks》 SCIE 2020年第4期514-523,共10页
Wireless Body Area Networks(WBANs)comprise various sensors to monitor and collect various vital signals,such as blood pressure,pulse,heartbeat,body temperature,and blood sugar.A dense and mobile WBAN often suffers fro... Wireless Body Area Networks(WBANs)comprise various sensors to monitor and collect various vital signals,such as blood pressure,pulse,heartbeat,body temperature,and blood sugar.A dense and mobile WBAN often suffers from interference,which causes serious problems,such as wasting energy and degrading throughput.In reality,not all of the sensors in WBAN need to be active at the same time.Therefore,they can be divided into different groups so that each group works in turn to avoid interference.In this paper,a Nest-Based WBAN Scheduling(NBWS)algorithm is proposed to cluster sensors of the same types in a single or multiple WBANs into different groups to avoid interference.Particularly,we borrow the graph coloring theory to schedule all groups to work using a Time Division for Multimodal Sensor(TDMS)group scheduling model.Both theoretical analysis and experimental results demonstrate that the proposed NBWS algorithm performs better in terms of frequency of collisions,transmission delay,system throughput,and energy consumption compared to the counterpart methods. 展开更多
关键词 Interference elimination NEST SENSORS SCHEDULING Wireless body area networks graph coloring theory
下载PDF
SRF Coloring:Stream Register File Allocation via Graph Coloring 被引量:1
9
作者 杨学军 邓宇 +5 位作者 汪黎 晏小波 杜静 张英 王桂彬 唐滔 《Journal of Computer Science & Technology》 SCIE EI CSCD 2009年第1期152-164,共13页
Stream Register File (SRF) is a large on-chip memory of the stream processor and its efficient management is essential for good performance. Current stream programming languages expose the management of SRF to the p... Stream Register File (SRF) is a large on-chip memory of the stream processor and its efficient management is essential for good performance. Current stream programming languages expose the management of SRF to the programmer, incurring heavy burden on the programmer and bringing difficulties to inheriting the legacy codes. SF95 is the language developed for FT64 which is the first 64-bit stream processor designed for scientific applications. SF95 conceals SRF from the programmer and leaves the management of SRF to its compiler. In this paper, we present a compiler approach named SRF Coloring to manage SRF automatically. The novelties of this paper are: first, it is the first time to use the graph coloring-based algorithm for the SRF management; second, an algorithm framework for SRF Coloring that is well suited to the FT64 architecture is proposed this framework is based on a well-understood graph coloring algorithm for register allocation, together with some modifications to deal with the unusual aspects of SRF problem; third, the SRF Coloring algorithm is implemented in SF95Compiler, a compiler designed for FT64 and SF95. The experimental results show that our approach represents a practical and promising solution to SRF allocation. 展开更多
关键词 memory management SRF coloring graph coloring stream processor stream register file compiler optimization
原文传递
Acyclic colorings of graphs with bounded degree 被引量:2
10
作者 FIEDOROWICZ Anna SIDOROWICZ Elzbieta 《Science China Mathematics》 SCIE CSCD 2016年第7期1427-1440,共14页
A k coloring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider... A k coloring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider some generalized acyclic k colorings, namely, we require that each color class induces an acyclic or bounded degree graph. Mainly we focus on graphs with maximum degree 5. We prove that any such graph has an acyclic 5 coloring such that each color class induces an acyclic graph with maximum degree at most 4. We prove that the problem of deciding whether a graph G has an acyclic 2 coloring in which each color class induces a graph with maximum degree at most 3 is NP complete, even for graphs with maximum degree 5. We also give a linear time algorithm for an acyclic t improper coloring of any graph with maximum degree d assuming that the number of colors is large enough. 展开更多
关键词 acyclic coloring bounded degree graph computational complexity
原文传递
VColor^(*):a practical approach for coloring large graphs
11
作者 Yun PENG Xin LIN +1 位作者 Byron CHOI Bingsheng HE 《Frontiers of Computer Science》 SCIE EI CSCD 2021年第4期133-149,共17页
Graph coloring has a wide range of real world applications,such as in the operations research,communication network,computational biology and compiler optimization fields.In our recent work[1],we propose a divide-andc... Graph coloring has a wide range of real world applications,such as in the operations research,communication network,computational biology and compiler optimization fields.In our recent work[1],we propose a divide-andconquer approach for graph coloring,called VColor.Such an approach has three generic subroutines.(i)Graph partition subroutine:VColor partitions a graph G into a vertex cut partition(VP),which comprises a vertex cut component(VCC)and small non-overlapping connected components(CCs).(ii)Component coloring subroutine:VColor colors the VCC and the CCs by efficient algorithms.(iii)Color combination subroutine:VColor combines the local colors by exploiting the maximum matchings of color combination bigraphs(CCBs).VColor has revealed some major bottlenecks of efficiency in these subroutines.Therefore,in this paper,we propose VColor^(*),an approach which addresses these efficiency bottlenecks without using more colors both theoretically and experimentally.The technical novelties of this paper are the following.(i)We propose the augmented VP to index the crossing edges of the VCC and the CCs and propose an optimized CCB construction algorithm.(ii)For sparse CCs,we propose using a greedy coloring algorithm that is of polynomial time complexity in the worst case,while preserving the approximation ratio.(iii)We propose a distributed graph coloring algorithm.Our extensive experimental evaluation on real-world graphs confirms the efficiency of VColor^(*).In particular,VColor^(*)is 20X and 50X faster than VColor and uses the same number of colors with VColor on the Pokec and PA datasets,respectively.VColor^(*)also significantly outperforms the state-ofthe-art graph coloring methods. 展开更多
关键词 graph coloring approximation algorithm distributed algorithm
原文传递
Application of CorelDRAW in Environmental Art Design
12
作者 ZHOU Pei 《Journal of Landscape Research》 2015年第6期87-88,90,共3页
CorelDRAW has particular uses in architectural design, interior design and landscape design. By comparing several software, it was found that CorelDRAW had the working plan drawing of AutoCAD, mapping of 3DMAX, and be... CorelDRAW has particular uses in architectural design, interior design and landscape design. By comparing several software, it was found that CorelDRAW had the working plan drawing of AutoCAD, mapping of 3DMAX, and better typesetting than Photoshop had, thus it plays an irreplaceable role in drawing working plan of environmental art design, especially colored plane and elevation view drawings. 展开更多
关键词 CORELDRAW AUTOCAD 3DMAX PHOTOSHOP Colored plane graph MAPPING
下载PDF
A Note on List Edge and List Total Coloring of Planar Graphs without Adjacent Short Cycles
13
作者 Hui Juan WANG Jian Liang WU 《Acta Mathematica Sinica,English Series》 SCIE CSCD 2014年第1期91-96,共6页
LetGbe a planar graph with maximum degreeΔ.In this paper,we prove that if any4-cycle is not adjacent to ani-cycle for anyi∈{3,4}in G,then the list edge chromatic numberχl(G)=Δand the list total chromatic number... LetGbe a planar graph with maximum degreeΔ.In this paper,we prove that if any4-cycle is not adjacent to ani-cycle for anyi∈{3,4}in G,then the list edge chromatic numberχl(G)=Δand the list total chromatic numberχl(G)=Δ+1. 展开更多
关键词 List edge coloring list total coloring planar graph cycle
原文传递
Edge choosability of planar graphs without short cycles 被引量:1
14
作者 WANG Weifan 《Science China Mathematics》 SCIE 2005年第11期1531-1544,共14页
In this paper we prove that if G is a planar graph with △= 5 and without 4-cycles or 6-cycles, then G is edge-6-choosable. This consequence together with known results show that, for each fixed k ∈{3,4,5,6}, a k-cyc... In this paper we prove that if G is a planar graph with △= 5 and without 4-cycles or 6-cycles, then G is edge-6-choosable. This consequence together with known results show that, for each fixed k ∈{3,4,5,6}, a k-cycle-free planar graph G is edge-(△+ 1)-choosable, where △ denotes the maximum degree of G. 展开更多
关键词 PLANAR graph coloring choosability cycle
原文传递
Compact n-Manifolds via(n+l)-Colored Graphs:a New Approach
15
作者 Luigi Grasselli Michele Mulazzani 《Algebra Colloquium》 SCIE CSCD 2020年第1期95-120,共26页
We introduce a representation via(n+l)-colored graphs of compact n-manifolds with(possibly empty)boundary,which appears to be very convenient for computer aided study and tabulation.Our construction is a generalizatio... We introduce a representation via(n+l)-colored graphs of compact n-manifolds with(possibly empty)boundary,which appears to be very convenient for computer aided study and tabulation.Our construction is a generalization to arbitrary dimension of the one recently given by Cristofori and Mulazzani in dimension three,and it is dual to the one given by Pezzana in the 1970s.In this context we establish some results concerning the topology of the represented manifolds:suspensions,fundamental groups,connected sums and moves between graphs representing the same manifold.Classification results of compact orientable 4-manifolds representable by graphs up to six vertices are obtained,together with some properties of the G-degree of 5-colored graphs relating this approach to tensor models theory. 展开更多
关键词 compact manifolds colored graphs fundamental groups dipole moves
原文传递
Rainbow and Monochromatic Vertex-connection of Random Graphs
16
作者 Wen-jing LI Hui JIANG Jia-bei HE 《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 2022年第4期966-972,共7页
A vertex-colored path P is rainbow if its internal vertices have distinct colors;whereas P is monochromatic if its internal vertices are colored the same.For a vertex-colored connected graph G,the rainbow vertex-conne... A vertex-colored path P is rainbow if its internal vertices have distinct colors;whereas P is monochromatic if its internal vertices are colored the same.For a vertex-colored connected graph G,the rainbow vertex-connection number rvc(G)is the minimum number of colors used such that there is a rainbow path joining any two vertices of G;whereas the monochromatic vertex-connection number mvc(G)is the maximum number of colors used such that any two vertices of G are connected by a monochromatic path.These two opposite concepts are the vertex-versions of rainbow connection number rc(G)and monochromatic connection number mc(G)respectively.The study on rc(G)and mc(G)of random graphs drew much attention,and there are few results on the rainbow and monochromatic vertex-connection numbers.In this paper,we consider these two vertex-connection numbers of random graphs and establish sharp threshold functions for them,respectively. 展开更多
关键词 graph coloring rainbow vertex-connection number monochromatic vertex-connection number random graphs threshold function
原文传递
Improved Upper Bounds on Acyclic Edge Colorings
17
作者 Yu-wen WU Gui-ying YAN 《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 2014年第2期305-308,共4页
An acyclic edge coloring of a graph is a proper edge coloring such that every cycle contains edges of at least three distinct colors. The acyclic chromatic index of a graph G, denoted by a'(G), is the minimum numbe... An acyclic edge coloring of a graph is a proper edge coloring such that every cycle contains edges of at least three distinct colors. The acyclic chromatic index of a graph G, denoted by a'(G), is the minimum number k such that there is an acyclic edge coloring using k colors. It is known that a'(G) ≤ 16△ for every graph G where △denotes the maximum degree of G. We prove that a'(G) 〈 13.8A for an arbitrary graph G. We also reduce the upper bounds of a'(G) to 9.8△ and 9△ with girth 5 and 7, respectively. 展开更多
关键词 graph coloring acyclic edge coloring Lovasz local lemma
原文传递
基于图着色理论的多飞艇多载荷协同对地观测和数据传输调度模型与算法 被引量:3
18
作者 周光辉 敬帅 梁伟 《系统工程理论与实践》 EI CSSCI CSCD 北大核心 2021年第9期2338-2354,共17页
临近空间平台是一类新兴的空间平台,可用于局部区域的对地观测.本文针对飞艇的特性和用户需求的复杂性,设计了多飞艇多载荷协同对地观测和数据传输体系,考虑常规观测任务的调度,以及应急观测任务的重调度.基于图着色理论(graph coloring... 临近空间平台是一类新兴的空间平台,可用于局部区域的对地观测.本文针对飞艇的特性和用户需求的复杂性,设计了多飞艇多载荷协同对地观测和数据传输体系,考虑常规观测任务的调度,以及应急观测任务的重调度.基于图着色理论(graph coloring theory,GCT),构建多飞艇多载荷协同对地观测和数据传输调度模型.将多飞艇协同对地观测与数据传输任务、任务间的冲突、以及飞艇和地面站分别映射为无向图中的点、边和颜色,从而将问题构建为图着色问题(graph coloring problem,GCP),最大化完成任务总收益的优化目标转换为GCP中最大化着色点收益.提出一种文化基因算法(memetic algorithm,MA),设计基于收益改进的禁忌搜索(Tabu search,TS)算子更新染色体,和对父代染色体中最大收益的连续基因进行遗传的交叉策略.数值实验结果表明,针对不同规模的算例,相较于TS和ILOG CPLEX,MA能够在合理时间内获得更满意的解. 展开更多
关键词 调度 对地观测 飞艇 图着色理论(graph coloring theory GCT) 文化基因算法(memetic algorithm MA)
原文传递
Managing Data-Objects in Dynamically Reconfigurable Caches
19
作者 杨学军 吴俊杰 +1 位作者 曾坤 唐玉华 《Journal of Computer Science & Technology》 SCIE EI CSCD 2010年第2期232-245,共14页
The widening gap between processor and memory speeds makes cache an important issue in the computer system design. Compared with work set of programs, cache resource is often rare. Therefore, it is very important for ... The widening gap between processor and memory speeds makes cache an important issue in the computer system design. Compared with work set of programs, cache resource is often rare. Therefore, it is very important for a computer system to use cache efficiently. Toward a dynamically reconfigurable cache proposed recently, DOOC (Data- Object Oriented Cache), this paper proposes a quantitative framework for analyzing the cache requirement of data-objects, which includes cache capacity, block size, associativity and coherence protocol. And a kind of graph coloring algorithm dealing with the competition between data-objects in the DOOC is proposed as well. Finally, we apply our approaches to the compiler management of DOOC. We test our approaches on both a single-core platform and a four-core platform. Compared with the traditional caches, the DOOC in both platforms achieves an average reduction of 44.98% and 49.69% in miss rate respectively. And its performance is very close to the ideal optimal cache. 展开更多
关键词 CACHE data-object data reuse data-object oriented cache (DOOC) graph coloring
原文传递
Novel scheme for interference avoidance in cognitive radio based cellular networks
20
作者 WANG Sai XU Xiao-dong +2 位作者 CHEN Xin TAO Xiao-feng WANG Qiang 《The Journal of China Universities of Posts and Telecommunications》 EI CSCD 2012年第1期69-76,共8页
The cognitive radio (CR) technology is believed to improve the spectrum efficiency. However, the interference problem has become a critical issue due to the coexistence of primary systems and CR systems. In this pap... The cognitive radio (CR) technology is believed to improve the spectrum efficiency. However, the interference problem has become a critical issue due to the coexistence of primary systems and CR systems. In this paper, the interferences in CR based cellular networks are discussed. Interference scenarios are analyzed, considering different interference sources. Meanwhile, an improved model named 'Cognitive Interference Ring' is introduced to describe the interference range of each secondary user (SU). Depending on the above analysis, graph coloring based dynamic power allocation (GCDPA) scheme is proposed for interference avoidance. Simulation results demonstrate that in CR based cellular networks, the interferences to primary users (PUs) can be effectively mitigated with the proposed GCDPA scheme, and the system throughput and power efficiency are both improved. 展开更多
关键词 CR interference analysis interference avoidance graph coloring power allocation cellular networks
原文传递
上一页 1 下一页 到第
使用帮助 返回顶部