Author name cluster

Mingyang Gong

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

I&C Journal 2026 Journal Article

Approximation algorithms for non-sequential star packing problems

Mengyuan Hu
An Zhang
Yong Chen
Mingyang Gong
Guohui Lin

For a positive integer k ≥ 1, a k-star ( k + -star, k − -star, respectively) is a connected graph containing a degree-ℓ vertex and ℓ degree-1 vertices, where ℓ = k ( ℓ ≥ k, 1 ≤ ℓ ≤ k, respectively). The k + -star packing problem is to cover as many vertices of an input graph G as possible using vertex-disjoint k + -stars in G; and given k > t ≥ 1, the k − / t -star packing problem is to cover as many vertices of G as possible using vertex-disjoint k − -stars but no t-stars in G. Both problems are NP-hard for any fixed k ≥ 2. We present a ( 1 + k 2 2 k + 1 ) - and a 3 2 -approximation algorithms for the k + -star packing problem when k ≥ 3 and k = 2, respectively, and a ( 1 + 1 t + 1 + 1 / k ) -approximation algorithm for the k − / t -star packing problem when k > t ≥ 2. They are all local search algorithms and they improve the best known approximation algorithms for the problems, respectively.

Details DOI

I&C Journal 2025 Journal Article

Approximation algorithms for the maximum path cover problem using long paths

Mingyang Gong
Yong Chen
Zhi-Zhong Chen
Guohui Lin
Bing Su
Lusheng Wang

The problem studied in this paper is to find a collection of vertex-disjoint paths in a given graph G = ( V, E ) such that each path has length at least k, called a long path, and the total number of edges on these paths is maximized. The problem is NP-hard for any fixed k or when k is part of the input, by a reduction from the Hamiltonian path problem. Berman and Karpinski presented a 7/6-approximation algorithm for k = 1, but for a general k ≥ 2, there is no approximation algorithm directly for the problem. We present the first local search ( 0. 4394 k + O ( 1 ) ) -approximation algorithm for any fixed k ≥ 1, and a 1. 4254-approximation algorithm for k = 2 built on top of a maximum triangle-free path-cycle cover.

Details DOI

TCS Journal 2025 Journal Article

Path cover using only short paths

Mingyang Gong
Guangting Chen
Zhi-Zhong Chen
Guohui Lin
Riki Uchida

We study a variant of the well-known Path Cover problem where the candidate paths in a solution have orders up to a fixed integer k. In Path Cover, one finds a minimum number of vertex-disjoint paths in an input graph to cover all the vertices; in our variant, not all paths but only those short ones, i. e. , containing up to k vertices, can be used as candidates. The problem is NP-hard when k ≥ 3; in the literature, there exist quite a number of approximation algorithms, especially for small k's. We present an improved k 3 -approximation algorithm for k ∈ { 6, 7, 8 }, an improved 55 31 -approximation algorithm for k = 5, and an improved 8 5 -approximation algorithm for k = 4. The novelty inside these improved algorithms is observing a close connection between an optimal path cover and a certain polynomial-time computed edge set.

Details DOI

MFCS Conference 2022 Conference Paper

Approximation Algorithms for Covering Vertices by Long Paths

Mingyang Gong
Jing Fan
Guohui Lin
Eiji Miyano

Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seemingly escapes from the literature. A path containing at least k vertices is considered long. When k ≤ 3, the problem is polynomial time solvable; when k is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed k ≥ 4, the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a k-approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when k = 4, the problem admits a 4-approximation algorithm which was presented recently. We propose the first (0. 4394 k + O(1))-approximation algorithm for the general problem and an improved 2-approximation algorithm when k = 4. Both algorithms are based on local improvement, and their performance analyses are done via amortization.

Details