期刊：
Lecture Notes in Computer Science,2019年11640:121-128 ISSN：0302-9743
通讯作者：
Fu, Bin
作者机构：
[Fu, Bin; Chen, Zhixiang] Univ Texas Rio Grande Valley, Dept Comp Sci, Edinburg, TX 78539 USA.;[Feng, Qilong; Wang, Jianxin] Cent Southern Univ, Sch Informat, Changsha, Peoples R China.;[Lin, Mugang] Hengyang Normal Univ, Sch Comp Sci & Technol, Hengyang, Peoples R China.
通讯机构：
[Fu, Bin] U;Univ Texas Rio Grande Valley, Dept Comp Sci, Edinburg, TX 78539 USA.
会议名称：
13th International Conference on Algorithmic Aspects in Information and Management (AAIM)
会议时间：
AUG 06-08, 2019
会议地点：
Beijing, PEOPLES R CHINA
会议主办单位：
[Chen, Zhixiang;Fu, Bin] Univ Texas Rio Grande Valley, Dept Comp Sci, Edinburg, TX 78539 USA.^[Feng, Qilong;Wang, Jianxin] Cent Southern Univ, Sch Informat, Changsha, Peoples R China.^[Lin, Mugang] Hengyang Normal Univ, Sch Comp Sci & Technol, Hengyang, Peoples R China.
会议论文集名称：
Lecture Notes in Computer Science
摘要：
In this paper, we develop an exponential time approximation scheme for the traveling salesman problem (TSP) on undirected graphs. If the weight of each edge is a nonnegative real number, then there is an algorithm to give an \((1+\epsilon )\) approximation for the TSP problem in \(O({1\over \epsilon }\cdot 1.66^n)\) and a polynomial space. It is in contrast to Golovnen’s approximation scheme for TSP on directed graphs with \(\mathrm{O}({1\over \epsilon }\cdot 2^n)\) time. We also show that there is no \(2^{o(n)}\) time constant factor approximation for the TSP problem under Exponential Time Hypothesis in complexity theory.
作者：
Mugang Lin;Jianxin Wang 0001;Qilong Feng;Bin Fu
期刊：
Algorithms,2019年12(2):50- ISSN：1999-4893
通讯作者：
Wang, Jianxin(jxwang@csu.edu.cn)
作者机构：
[Mugang Lin; Jianxin Wang 0001; Qilong Feng] School of Computer Science and Engineering, Central South University, Changsha;410083, China;School of Computer Science and Technology, Hengyang Normal University, Hengyang;421002, China;Hunan Provincial Key Laboratory of Intelligent Information Processing and Application, Hengyang
通讯机构：
[Jianxin Wang] S;School of Computer Science and Engineering, Central South University, Changsha 410083, China<&wdkj&>Author to whom correspondence should be addressed.
期刊：
Information Processing Letters,2018年136:30-36 ISSN：0020-0190
通讯作者：
Feng, Qilong
作者机构：
[Feng, Qilong; Lin, Mugang; Wang, Jianxin] Cent S Univ, Sch Informat Sci & Engn, Changsha, Hunan, Peoples R China.;[Lin, Mugang] Hengyang Normal Univ, Sch Comp Sci & Technol, Hengyang, Peoples R China.;[Lin, Mugang] Hunan Prov Key Lab Intelligent Informat Proc & Ap, Hengyang, Peoples R China.;[Chen, Jianer] Texas A&M Univ, Dept Comp Sci & Engn, College Stn, TX 77843 USA.;[Fu, Bin] Univ Texas Rio Grande Valley, Dept Comp Sci, Edinburg, TX USA.
通讯机构：
[Feng, Qilong] C;Cent S Univ, Sch Informat Sci & Engn, Changsha, Hunan, Peoples R China.
关键词：
Almost forest deletion;Feedback vertex set;Fixed-parameter algorithm;Graph algorithms;Iterative compression
摘要：
Almost Forest Deletion problem (AFD) is a generalization of the Feedback Vertex Set problem, which decides whether there exist at most k vertices in a given graph G whose removal from G results in an l-forest, where k and l are two given non-negative integers, and an l-forest is a graph which can be transformed into a forest by deleting at most l edges. Based on the iterative compression technique, we study the iterative version of the AFD problem, called Almost Forest Deletion Disjoint Compression problem (AFDDC), which asks for a new l-forest deletion set X′ of size at most k for a given graph G that is disjoint with a given l-forest deletion set X of graph G for two given non-negative integers k and l. For the AFDDC problem, we develop some reduction rules to simplify a given instance, and give a new branching algorithm for the problem. A new branching measure is presented to evaluate the efficiency of the algorithm, which results in an algorithm of running time O⁎(4k+l). Based on the proposed algorithm for the AFDDC problem, a parameterized algorithm for the AFD problem with running time O⁎(5k4l) is presented, improving the previous result O⁎(5.0024(k+l)).
期刊：
Lecture Notes in Computer Science,2018年10976:726-737 ISSN：0302-9743
通讯作者：
Feng, Qilong
作者机构：
[Feng, Qilong; Lin, Mugang] Cent S Univ, Sch Informat Sci & Engn, Changsha, Hunan, Peoples R China.;[Lin, Mugang] Hengyang Normal Univ, Sch Comp Sci & Technol, Hengyang, Peoples R China.;[Lin, Mugang] Hunan Prov Key Lab Intelligent Informat Proc & Ap, Hengyang, Peoples R China.;[Fu, Bin] Univ Texas Rio Grande Valley, Dept Comp Sci, Edinburg, TX 78539 USA.
通讯机构：
[Feng, Qilong] C;Cent S Univ, Sch Informat Sci & Engn, Changsha, Hunan, Peoples R China.
会议名称：
24th International Computing and Combinatorics Conference (COCOON)
会议时间：
JUL 02-04, 2018
会议地点：
Qing Dao, PEOPLES R CHINA
会议主办单位：
[Lin, Mugang;Feng, Qilong] Cent S Univ, Sch Informat Sci & Engn, Changsha, Hunan, Peoples R China.^[Lin, Mugang] Hengyang Normal Univ, Sch Comp Sci & Technol, Hengyang, Peoples R China.^[Lin, Mugang] Hunan Prov Key Lab Intelligent Informat Proc & Ap, Hengyang, Peoples R China.^[Fu, Bin] Univ Texas Rio Grande Valley, Dept Comp Sci, Edinburg, TX 78539 USA.
会议论文集名称：
Lecture Notes in Computer Science
关键词：
Approximation algorithm;l-Pseudoforest Deletion problem;Local ratio
摘要：
An l-pseudoforest is a graph each of whose connected component is at most l edges away from being a tree. The l-Pseudoforest Deletion problem is to delete a vertex set P of minimum weight from a given vertex-weighted graph \(G=(V,E)\) such that the remaining graph \(G[V\setminus P]\) is an l-pseudoforest. The Feedback Vertex Set problem is a special case of the l-Pseudoforest Deletion problem with \(l=0\). In this paper, we present a polynomial time 4l-approximation algorithm for the l-Pseudoforest Deletion problem with \(l\ge 1\) by using the local ratio technique. When \(l=1\), we get a better approximation ratio 2 for the problem by further analyzing the algorithm, which matches the current best constant approximation factor for the Feedback Vertex Set problem.
摘要：
Network reconfiguration is an important research topic in the planning and operation of power distribution networks. In this paper, we study the partition problem on trees with supply and demand from parameterized computation perspective. We analyze the relationship between supply nodes and demand nodes, and give four reduction rules, which result in a kernel of size O(k(2)) for the problem. Based on branching technique, a parameterized algorithm of running time O*(2.828(k)) is presented. (C) 2016 Published by Elsevier B.V.
期刊：
International Journal of Distributed Sensor Networks,2015年2015(10):437678:1-437678:13 ISSN：1550-1477
通讯作者：
Liu, Fangju
作者机构：
[Liu, Fangju] Univ South China, Sch Comp Sci & Technol, Hengyang 421001, Hunan, Peoples R China.;[Ma, Xingpo] Xinyang Normal Univ, Sch Comp & Informat Technol, Xinyang 464000, Henan, Peoples R China.;[Liang, Junbin] Guangxi Univ, Sch Comp & Elect Informat, Nanning 530004, Guangxi, Peoples R China.;[Lin, Mugang] Hengyang Normal Univ, Dept Comp Sci, Hengyang 421008, Hunan, Peoples R China.
通讯机构：
[Liu, Fangju] U;Univ South China, Sch Comp Sci & Technol, Hengyang 421001, Hunan, Peoples R China.
摘要：
Verifiable top-k query processing in tiered sensor networks, which refers to verifying the authenticity and the completeness of top-k query results received by the network owner in tiered sensor networks, has received attention in very recent years. However, the existing solutions of this problem are only fit for static sensor network. In this paper, we try to solve the problem in a tiered mobile sensor network model, where not only static sensor nodes but also mobile sensor nodes existed. Based on the tiered mobile sensor network model, we propose a novel verifiable scheme named VTMSN for fine-grained top-k queries. The main idea of VTMSN is as follows: it maps each of the positions where sensor nodes are in a static state to a virtual node and then establishes relationships among data items of each virtual node with their score orders, which are encrypted along with the scores of the data items and the time epochs using the distinct symmetric keys kept by each sensor node and the network owner. Both theory analysis and simulation results show the efficiency and the security of VTMSN.
作者机构：
[Mugang Lin; Jianxin Wang; Qilong Feng] School of Information Science and Engineering,Central South University,Changsha 410083,China;[Mugang Lin] Department of Computer Science,Hengyang Normal University,Hengyang 421002,China
摘要：
Kidney exchange programs have been established in several countries to organize kidney exchanges between incompatible patient-donor pairs.The core of these programs are algorithms to solve kidney exchange problem, which can be modeled as finding a maximum weight packing of vertex-disjoint cycles with length at most some small constant L (typically 2 ≤ L ≤ 5) in a directed graph.In generally, the objective function is maximizing the number of possible kidney transplants.In this paper, we study the random methods for the kidney exchange problem involving only 2-cycle and 3-cycle exchanges.First, we formal the kidney exchange problem as a parameterized model.And then we propose a randomized parameterized algorithm of running time O*(5.63k3 · 22k2) by randomly partitioning the vertices.Last, by using the random divide-and-conquer technique, another randomized algorithm of running time O* (k2[log k2/2.k3[logk3]/2.42k3.22k2) is given for the parameterized kidney problem.Moreover,our randomized algorithms can be extended to solve the general kidney exchange problem.
