具有长度约束的简单路径(Simple Paths with Length Constraint,SPLC)问题是指求解图中任意两点间路径长度为m的简单路径数,是k-path问题的一种特殊情况.该文基于网树数据结构提出了在有向无环图中求解SPLC问题的算法(Nettree for SPLC ...具有长度约束的简单路径(Simple Paths with Length Constraint,SPLC)问题是指求解图中任意两点间路径长度为m的简单路径数,是k-path问题的一种特殊情况.该文基于网树数据结构提出了在有向无环图中求解SPLC问题的算法(Nettree for SPLC in Directed Acyclic Graphs,NSPLCDAG).网树是一种多树根多双亲的数据结构.NSPLCDAG算法将该问题转化为一棵网树后,利用树根路径数这一性质对其进行求解.对NSPLCDAG算法进行改造,可以求解有向无环图中最长路径问题并形成网树求解最长路径算法(Nettree for the Longest Path inDAGs,NLPDAG),NLPDAG算法可找到所有最长路径,对NLPDAG算法做进一步改进形成改进的NLPDAG算法,改进的NLPDAG算法可在线性时间复杂度内给出有向无环图中的一条最长路径.实验结果验证了NSPLCDAG和改进的NLPDAG算法的正确性与有效性.展开更多
A graph G is {K1,4, K1,4 ＋ e}-free if G contains no induced subgraph isomorphic to K1,4 or KI,a ＋ e In this paper, we show that G has a path which is either hamiltonian or of length at least 25（G） ＋ 2 if G is a c...A graph G is {K1,4, K1,4 ＋ e}-free if G contains no induced subgraph isomorphic to K1,4 or KI,a ＋ e In this paper, we show that G has a path which is either hamiltonian or of length at least 25（G） ＋ 2 if G is a connected {K1,4, K1,4 ＋ e}-free graph on at least 7 vertices.展开更多
For a graph G, we denote by p（G） and c（G） the number of vertices of a longest path and a longest cycle in G, respectively. For a vertex v in G, id（v） denotes the implicit degree of v. In this paper, we obtain th...For a graph G, we denote by p（G） and c（G） the number of vertices of a longest path and a longest cycle in G, respectively. For a vertex v in G, id（v） denotes the implicit degree of v. In this paper, we obtain that if G is a 2-connected graph on n vertices such that the implicit degree sum of any three independent vertices is at least n ＋ 1, then either G contains a hamiltonian path, or c（G） 〉 p（G） - 1.展开更多
任务调度算法的研究一直是异构计算技术研究中的热点,充分挖掘异构处理平台的并行优势,可最大限度实现平台资源的高效利用。通过分析异构处理平台的执行特点,设计符合异构处理平台的任务调度策略,提出面向异构处理平台的最长路径列表调...任务调度算法的研究一直是异构计算技术研究中的热点,充分挖掘异构处理平台的并行优势,可最大限度实现平台资源的高效利用。通过分析异构处理平台的执行特点,设计符合异构处理平台的任务调度策略,提出面向异构处理平台的最长路径列表调度算法(Longest path list scheduling algorithm,LPLS)。算法在任务优先级阶段,基于最长路径列表计算优先级,最耗时路径上的任务被优先调度;在处理器选择阶段,遵循任务完成时间最小的原则,所选择的处理器可使下阶段任务的完成时间更短,异构平台整体处理时间更小。仿真实验结果表明,相比于经典的HEFT算法,LPLS算法是一种负载更加均衡的算法,具有调度长度更短、效率更高等优势。展开更多
We say that a parameter p of directed graphs has the interval property if for every graph G?and orientations of G, p can take every value between its minimum and maximum values. Let λbe the length of the lo...We say that a parameter p of directed graphs has the interval property if for every graph G?and orientations of G, p can take every value between its minimum and maximum values. Let λbe the length of the longest directed path. A question asked by C. Lin in [1] is equivalent to the question of whether λhas the interval property. In this note, we answer this question in the affirmative. We also show that the diameter of directed graphs does not have the interval property.展开更多
文摘具有长度约束的简单路径(Simple Paths with Length Constraint,SPLC)问题是指求解图中任意两点间路径长度为m的简单路径数,是k-path问题的一种特殊情况.该文基于网树数据结构提出了在有向无环图中求解SPLC问题的算法(Nettree for SPLC in Directed Acyclic Graphs,NSPLCDAG).网树是一种多树根多双亲的数据结构.NSPLCDAG算法将该问题转化为一棵网树后,利用树根路径数这一性质对其进行求解.对NSPLCDAG算法进行改造,可以求解有向无环图中最长路径问题并形成网树求解最长路径算法(Nettree for the Longest Path inDAGs,NLPDAG),NLPDAG算法可找到所有最长路径,对NLPDAG算法做进一步改进形成改进的NLPDAG算法,改进的NLPDAG算法可在线性时间复杂度内给出有向无环图中的一条最长路径.实验结果验证了NSPLCDAG和改进的NLPDAG算法的正确性与有效性.
基金Supported by Scientific Research Program of the Higher Education Institution of Xinjiang (Grant No. 2011S30)Science Foundation of Xinjiang Normal University
文摘A graph G is {K1,4, K1,4 ＋ e}-free if G contains no induced subgraph isomorphic to K1,4 or KI,a ＋ e In this paper, we show that G has a path which is either hamiltonian or of length at least 25（G） ＋ 2 if G is a connected {K1,4, K1,4 ＋ e}-free graph on at least 7 vertices.
基金supported by the National Natural Science Foundation of China(Grant No.11501322)the Postdoctoral Science Foundation of China(Grant No.2015M571999)the Natural Science Foundation of Shandong Province(Grant No.ZR2014AP002)
文摘For a graph G, we denote by p（G） and c（G） the number of vertices of a longest path and a longest cycle in G, respectively. For a vertex v in G, id（v） denotes the implicit degree of v. In this paper, we obtain that if G is a 2-connected graph on n vertices such that the implicit degree sum of any three independent vertices is at least n ＋ 1, then either G contains a hamiltonian path, or c（G） 〉 p（G） - 1.
文摘任务调度算法的研究一直是异构计算技术研究中的热点,充分挖掘异构处理平台的并行优势,可最大限度实现平台资源的高效利用。通过分析异构处理平台的执行特点,设计符合异构处理平台的任务调度策略,提出面向异构处理平台的最长路径列表调度算法(Longest path list scheduling algorithm,LPLS)。算法在任务优先级阶段,基于最长路径列表计算优先级,最耗时路径上的任务被优先调度;在处理器选择阶段,遵循任务完成时间最小的原则,所选择的处理器可使下阶段任务的完成时间更短,异构平台整体处理时间更小。仿真实验结果表明,相比于经典的HEFT算法,LPLS算法是一种负载更加均衡的算法,具有调度长度更短、效率更高等优势。
文摘We say that a parameter p of directed graphs has the interval property if for every graph G?and orientations of G, p can take every value between its minimum and maximum values. Let λbe the length of the longest directed path. A question asked by C. Lin in [1] is equivalent to the question of whether λhas the interval property. In this note, we answer this question in the affirmative. We also show that the diameter of directed graphs does not have the interval property.
