In the minimum degree vertex deletion problem,we are given a graph,a distinguished vertex in the graph,and an integer κ,and the question is whether we can delete at most κ vertices from the graph so that the disting...In the minimum degree vertex deletion problem,we are given a graph,a distinguished vertex in the graph,and an integer κ,and the question is whether we can delete at most κ vertices from the graph so that the distinguished vertex has the unique minimum degree.The maximum degree vertex deletion problem is defined analogously but here we want the distinguished vertex to have the unique maximum degree.It is known that both problems areΨ-hard and fixed-parameter intractable with respect to some natural parameters.In this paper,we study the(parameterized)complexity of these two problems restricted to split graphs,p-degenerate graphs,and planar graphs.Our study provides a comprehensive complexity landscape of the two problems restricted to these special graphs.展开更多
A graph is said to be K1,4-free if it does not contain an induced subgraph isomorphic to K1,4. Let κ be an integer with κ ≥ 2. We prove that if G is a K1,4-free graph of order at least llκ- 10 with minimum degree ...A graph is said to be K1,4-free if it does not contain an induced subgraph isomorphic to K1,4. Let κ be an integer with κ ≥ 2. We prove that if G is a K1,4-free graph of order at least llκ- 10 with minimum degree at least four, then G contains k vertex-disjoint copies of K1 ＋ （K1 ∪ KK2）.展开更多
The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with...The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a graph.No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale.However,several algorithms are proposed that solve the problem approximately in a short polynomial time scale.Such algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational resources.The MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising etc.This work aims to solve the MVCP approximately by a novel graph decomposition approach.The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths.In order to reduce complexity of the algorithm a new strategy is also proposed.The reduction strategy can be used for any algorithm solving MVCP.Based on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the MVCP.These algorithms are tested using well known standard benchmark graphs.The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.展开更多
A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K1,3. Let K4 be the graph obtained by removing exactly one edge from K4 and let k be an integer with k ≥ 2. We prove that if G ...A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K1,3. Let K4 be the graph obtained by removing exactly one edge from K4 and let k be an integer with k ≥ 2. We prove that if G is a claw-free graph of order at least 13k - 12 and with minimum degree at least five, then G contains k vertex-disjoint copies of K4. The requirement of number five is necessary.展开更多
该文针对发射阵列、接收阵列以及多级延迟器均为非均匀配置的双基地MIMO雷达,提出基于时域和空域二次自由度扩展的发射角、接收角以及多普勒频率估计的ESPRIT(Estimating Signal Via Rotational Invariance Techniques)新方法。该方法...该文针对发射阵列、接收阵列以及多级延迟器均为非均匀配置的双基地MIMO雷达,提出基于时域和空域二次自由度扩展的发射角、接收角以及多普勒频率估计的ESPRIT(Estimating Signal Via Rotational Invariance Techniques)新方法。该方法利用双基地MIMO雷达特殊的方向矢量特点(矩阵的Khatri-Rao积形式),对接收信号进行两次行置换以及去冗余处理,实现了时域和空域孔径自由度的二次扩展。然后对新数据进行时空"滑窗"处理,利用ESPRIT算法分别估计出目标的收发角以及多普勒频率。理论和仿真结果表明:在相同阵元和延迟级数情况下,所提算法的估计性能优于四线性分解和多维ESPRIT算法,且能估计出更多的目标,此外,通过最小冗余配置,极大地降低了阵列和延迟器的配置需求,更利于实际工程应用。展开更多
文摘In the minimum degree vertex deletion problem,we are given a graph,a distinguished vertex in the graph,and an integer κ,and the question is whether we can delete at most κ vertices from the graph so that the distinguished vertex has the unique minimum degree.The maximum degree vertex deletion problem is defined analogously but here we want the distinguished vertex to have the unique maximum degree.It is known that both problems areΨ-hard and fixed-parameter intractable with respect to some natural parameters.In this paper,we study the(parameterized)complexity of these two problems restricted to split graphs,p-degenerate graphs,and planar graphs.Our study provides a comprehensive complexity landscape of the two problems restricted to these special graphs.
基金Supported by National Natural Science Foundation of China(Grant Nos.11161035 and 11226292)Ningxia Ziran(Grant No.NZ1153)research grant from Ningxia University(Grant No.zr1122)
文摘A graph is said to be K1,4-free if it does not contain an induced subgraph isomorphic to K1,4. Let κ be an integer with κ ≥ 2. We prove that if G is a K1,4-free graph of order at least llκ- 10 with minimum degree at least four, then G contains k vertex-disjoint copies of K1 ＋ （K1 ∪ KK2）.
文摘The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a graph.No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale.However,several algorithms are proposed that solve the problem approximately in a short polynomial time scale.Such algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational resources.The MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising etc.This work aims to solve the MVCP approximately by a novel graph decomposition approach.The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths.In order to reduce complexity of the algorithm a new strategy is also proposed.The reduction strategy can be used for any algorithm solving MVCP.Based on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the MVCP.These algorithms are tested using well known standard benchmark graphs.The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.
基金This work was supported in part by the National Natural Science Foundation of China （Grant Nos. 11161035, 11401455） and the Fundamental Research Funds for the Central Universities （No. K5051370010）.
文摘A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K1,3. Let K4 be the graph obtained by removing exactly one edge from K4 and let k be an integer with k ≥ 2. We prove that if G is a claw-free graph of order at least 13k - 12 and with minimum degree at least five, then G contains k vertex-disjoint copies of K4. The requirement of number five is necessary.
文摘该文针对发射阵列、接收阵列以及多级延迟器均为非均匀配置的双基地MIMO雷达,提出基于时域和空域二次自由度扩展的发射角、接收角以及多普勒频率估计的ESPRIT(Estimating Signal Via Rotational Invariance Techniques)新方法。该方法利用双基地MIMO雷达特殊的方向矢量特点(矩阵的Khatri-Rao积形式),对接收信号进行两次行置换以及去冗余处理,实现了时域和空域孔径自由度的二次扩展。然后对新数据进行时空"滑窗"处理,利用ESPRIT算法分别估计出目标的收发角以及多普勒频率。理论和仿真结果表明:在相同阵元和延迟级数情况下,所提算法的估计性能优于四线性分解和多维ESPRIT算法,且能估计出更多的目标,此外,通过最小冗余配置,极大地降低了阵列和延迟器的配置需求,更利于实际工程应用。
