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.展开更多
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.展开更多
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.展开更多
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].展开更多
Oscillatory neural networks(ONNs)can handle image processing and combinational optimization problems with high biological plausibility.Coupled oscillators in ONNs mimic the neuronal oscillations and communication in t...Oscillatory neural networks(ONNs)can handle image processing and combinational optimization problems with high biological plausibility.Coupled oscillators in ONNs mimic the neuronal oscillations and communication in the human brain.In this study,we demonstrate edge detection and graph coloring using a network of oscillatory neuromorphic devices comprising silicon nanosheet(NS)-gated diodes and series resistors.Silicon NS-gated diodes modulate the energy band structure in the channel through electrostatic doping,which tunes the amplitude and frequency of the oscillatory neuromorphic devices.Coupled oscillatory neuromorphic devices with capacitors can be in-or out-of-phase,enabling edge detection.Horizontal and vertical edge detections were performed using the coupling configuration.Furthermore,an ONN using oscillatory neuromorphic devices with resistive and capacitive couplings can solve graph coloring problems by representing the coloring solutions as phase differences.This study provides a method for achieving a compact silicon-based ONN that acts as a solver machine,as well as an image processor.展开更多
Given two graphs G and H,the Ramsey number R(G,H)is the smallest positive integer N such that every 2-coloring of the edges of K_(N)contains either a red G or a blue H.Let K_(N-1)■K_(1,k)be the graph obtained from K_...Given two graphs G and H,the Ramsey number R(G,H)is the smallest positive integer N such that every 2-coloring of the edges of K_(N)contains either a red G or a blue H.Let K_(N-1)■K_(1,k)be the graph obtained from K_(N-1)by adding anew vertexνconnecting k vertices of K_(N-1).A graph G withχ(G)=k+1 is called edge-critical if G contains an edge e such thatχ(G-e)=k.A considerable amount of research has been conducted by previous scholars on Ramsey numbers ofgraphs.In this study,we show that for an edge-critical graph G with x(G)=k+1,when k≥2,1≥2,and n is sufficiently large,R(G,K_(1)+nK_(t))=knt+1 and r,(G,K_(1)+nK_(t))=(k-1)nt+1.展开更多
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.展开更多
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.展开更多
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.展开更多
In this paper,we survey known results on color-critical graphs in special graph classes.A graph is k-critical if its chromatic number is k but any proper subgraph of it has chromatic number less than k.For a family H ...In this paper,we survey known results on color-critical graphs in special graph classes.A graph is k-critical if its chromatic number is k but any proper subgraph of it has chromatic number less than k.For a family H of graphs,a graph is H-free if it does not contain H as an induced subgraph for every H∈H.A graph class is hereditary if it is H-free for some set H of graphs,and the graphs in H are called forbidden induced subgraphs for the class.We will focus on the characterization problem and the finiteness problem for hereditary graph classes that can be defined by one or two forbidden induced subgraphs.The characterization problem seeks a complete characterization of k-critical graphs in a given graph class and the finiteness problem asks if the number of k-critical graphs in a given class is finite.We shall survey results for both problems with an emphasis on how the results develop over the time and on the techniques used for proving results in the area.We also list important open problems and give some conjectures.展开更多
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.展开更多
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.展开更多
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.展开更多
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.展开更多
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.展开更多
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.展开更多
A specialized computer named as the Electronic Probe Computer(EPC)has been developed to address large-scale NP-complete problems.The EPC employs a hybrid serial/parallel computational model,structured around four main...A specialized computer named as the Electronic Probe Computer(EPC)has been developed to address large-scale NP-complete problems.The EPC employs a hybrid serial/parallel computational model,structured around four main subsystems:a converting system,an input/output system,and an operating system.The converting system is a software component that transforms the target problem into the graph coloring problem,while the operating system is designed to solve these graph coloring challenges.Comprised of 60 probe computing cards,this system is referred to as EPC60.In tackling large-scale graph coloring problems with EPC60,1003-colorable graphs were randomly selected,each consisting of 2,000 vertices.The state-of-the-art mathematical optimization solver achieved a success rate of only 6%,while EPC60 excelled with a remarkable 100%success rate.Additionally,EPC60 successfully solved two 3-colorable graphs with 1,500 and 2,000 vertices,which had eluded Gurobi’s attempts for 15 days on a standard workstation.Given the mutual reducibility of NP-complete problems in polynomial time theoretically,the EPC stands out as a universal solver for NP-complete problem.The EPC can be applied to various problems that can be abstracted as combinatorial optimization issues,making it relevant across multiple domains,including supply chain management,financial services,telecommunications,energy systems,manufacturing,and beyond.展开更多
In the field of wireless body area networks(WBANs),for solving the complex interference problem of inter-WBANs,a density-based adaptive optimization strategy(DAOS)is proposed in this paper.Firstly,the complex interfer...In the field of wireless body area networks(WBANs),for solving the complex interference problem of inter-WBANs,a density-based adaptive optimization strategy(DAOS)is proposed in this paper.Firstly,the complex interference problem among WBANs is converted into a distance-based graph coloring model,then time division multiple access and a two-level split clustering methods are adopted to allocate initial time slots for nodes.Secondly,the particle swarm optimization algorithm is used to optimize the time slot of each node for maximizing the throughput.We simulate the scenario on MATLAB simulator.Experimental results show that compared with the traditional scheme in high-density healthcare Internet of Things(IoT)scenarios,DAOS has obvious advantages compared with three comparison strategies of faster convergence rate of 48.94%,60.76%,and 96.82%,and higher throughput of 5.60%,8.08%,and 8.05%in traffic priorities 7 to 4.展开更多
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.展开更多
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.展开更多
基金This work was supported by the National Natural Science Foundation of China （Nos. G61374065, G61034007, G61374002） the Fund for the Taishan Scholar Project of Shandong Province, the Natural Science Foundation of Shandong Province （No. ZR2010FM013） the Scientific Research and Development Project of Shandong Provincial Education Department （No. J11LA01 ）
文摘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.
基金supported by the National Natural Science Foundation of China (60775047)Hunan Provincial Natural Science Foundation of China (07JJ6111)
文摘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.
基金supported by the National Natural Science Foundation of China (Grants Nos. 61072139,61072106,61203303,61003198,61272279,and 61003199)
文摘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.
文摘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].
基金partly supported by a National Research Foundation of Korea(NRF)grant funded by the Korean government(Nos.2022M3I7A3046571 and 2023RS00260876)the Brain Korea 21 Plus Project through the NRF funded by the Ministry of Science,ICT and Future Planning,Samsung Electronics(No.IO201223-08257-01)a Korea University Grant.
文摘Oscillatory neural networks(ONNs)can handle image processing and combinational optimization problems with high biological plausibility.Coupled oscillators in ONNs mimic the neuronal oscillations and communication in the human brain.In this study,we demonstrate edge detection and graph coloring using a network of oscillatory neuromorphic devices comprising silicon nanosheet(NS)-gated diodes and series resistors.Silicon NS-gated diodes modulate the energy band structure in the channel through electrostatic doping,which tunes the amplitude and frequency of the oscillatory neuromorphic devices.Coupled oscillatory neuromorphic devices with capacitors can be in-or out-of-phase,enabling edge detection.Horizontal and vertical edge detections were performed using the coupling configuration.Furthermore,an ONN using oscillatory neuromorphic devices with resistive and capacitive couplings can solve graph coloring problems by representing the coloring solutions as phase differences.This study provides a method for achieving a compact silicon-based ONN that acts as a solver machine,as well as an image processor.
基金supported by the National Key Research and Development Program of China(2023YFA1010200,2020YFA0713100)the National Natural Science Foundation of China(12071453)the Innovation Program for Quantum Science and Technology(2021ZD0302902).
文摘Given two graphs G and H,the Ramsey number R(G,H)is the smallest positive integer N such that every 2-coloring of the edges of K_(N)contains either a red G or a blue H.Let K_(N-1)■K_(1,k)be the graph obtained from K_(N-1)by adding anew vertexνconnecting k vertices of K_(N-1).A graph G withχ(G)=k+1 is called edge-critical if G contains an edge e such thatχ(G-e)=k.A considerable amount of research has been conducted by previous scholars on Ramsey numbers ofgraphs.In this study,we show that for an edge-critical graph G with x(G)=k+1,when k≥2,1≥2,and n is sufficiently large,R(G,K_(1)+nK_(t))=knt+1 and r,(G,K_(1)+nK_(t))=(k-1)nt+1.
基金Supported by the National Natural Science Foundation of China under Grant Nos.60621003 and 60633050.
文摘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.
基金supported by Taif University with Research Grant(TURSP-2020/77).
文摘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.
文摘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.
文摘In this paper,we survey known results on color-critical graphs in special graph classes.A graph is k-critical if its chromatic number is k but any proper subgraph of it has chromatic number less than k.For a family H of graphs,a graph is H-free if it does not contain H as an induced subgraph for every H∈H.A graph class is hereditary if it is H-free for some set H of graphs,and the graphs in H are called forbidden induced subgraphs for the class.We will focus on the characterization problem and the finiteness problem for hereditary graph classes that can be defined by one or two forbidden induced subgraphs.The characterization problem seeks a complete characterization of k-critical graphs in a given graph class and the finiteness problem asks if the number of k-critical graphs in a given class is finite.We shall survey results for both problems with an emphasis on how the results develop over the time and on the techniques used for proving results in the area.We also list important open problems and give some conjectures.
基金the Ningbo International Science and Technology Cooperation Programme(2016D10008)the Ningbo Key Science and Technology plan(2025)projects(2018B10075,2019B10125,2019B10028)+2 种基金the Marine Biotechnology and Marine Engineering Discipline Group(422004582)the Project of Research and Development of Intelligent Resource Allocation and Sharing Platform for Marine Electronic Information Industry(2017GY116)the Key science and technology projects of Zhejiang Province(2020C03064).
文摘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.
基金the support of NSF of China(61773167,61929103)NSF of Shandong Province(ZR2019LZH006)+1 种基金NSF of Shanghai(17ZR1444900,HKRGC GRF 12201119,12232716 and 12201518)QLUT Young Scholar Program(2018DBSHZ005).
文摘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.
基金supported by the Minister of Science and Higher Education of Poland (Grant No. JP2010009070)
文摘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.
基金supported by National Natural Science Foundation of China (No.60774007) and the Royal Society of UK
文摘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.
文摘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.
基金Supported by National Natural Science Foundation of China(Grant Nos.11201440 and 11271006)Graduate Independent Innovation Foundation of Shandong University(Grant No.yzc12100)
文摘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.
基金supported by the National Major Research Instrument Development Project(62427811)the Key Program of the National Natural Science Foundation of China(62332006)the General Program of the National Natural Science Foundation of China(62172014).
文摘A specialized computer named as the Electronic Probe Computer(EPC)has been developed to address large-scale NP-complete problems.The EPC employs a hybrid serial/parallel computational model,structured around four main subsystems:a converting system,an input/output system,and an operating system.The converting system is a software component that transforms the target problem into the graph coloring problem,while the operating system is designed to solve these graph coloring challenges.Comprised of 60 probe computing cards,this system is referred to as EPC60.In tackling large-scale graph coloring problems with EPC60,1003-colorable graphs were randomly selected,each consisting of 2,000 vertices.The state-of-the-art mathematical optimization solver achieved a success rate of only 6%,while EPC60 excelled with a remarkable 100%success rate.Additionally,EPC60 successfully solved two 3-colorable graphs with 1,500 and 2,000 vertices,which had eluded Gurobi’s attempts for 15 days on a standard workstation.Given the mutual reducibility of NP-complete problems in polynomial time theoretically,the EPC stands out as a universal solver for NP-complete problem.The EPC can be applied to various problems that can be abstracted as combinatorial optimization issues,making it relevant across multiple domains,including supply chain management,financial services,telecommunications,energy systems,manufacturing,and beyond.
基金supported by the National Natural Science Foundation of China(No.61761007)Guangxi Natural Science Foundation(No.2025GXNSFAA069734).
文摘In the field of wireless body area networks(WBANs),for solving the complex interference problem of inter-WBANs,a density-based adaptive optimization strategy(DAOS)is proposed in this paper.Firstly,the complex interference problem among WBANs is converted into a distance-based graph coloring model,then time division multiple access and a two-level split clustering methods are adopted to allocate initial time slots for nodes.Secondly,the particle swarm optimization algorithm is used to optimize the time slot of each node for maximizing the throughput.We simulate the scenario on MATLAB simulator.Experimental results show that compared with the traditional scheme in high-density healthcare Internet of Things(IoT)scenarios,DAOS has obvious advantages compared with three comparison strategies of faster convergence rate of 48.94%,60.76%,and 96.82%,and higher throughput of 5.60%,8.08%,and 8.05%in traffic priorities 7 to 4.
基金supported by the National Natural Science Foundation of China(Nos.11901196)Natural Science Foundation of Anhui Province(Nos.JZ2020AKZR0295)by the Scholarship Promotion Program of Hefei University of Technology(Nos.JZ2019HGTA0038)。
文摘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.
基金Supported by the National Natural Science Foundation of China(No.11371355)
文摘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.
