.png){kind=icon}
.png){kind=icon}
Return
Incremental algorithms for the maximum internal spanning tree problem
.png){kind=icon}
OA
AI
DOI：10.1007/s11432-019-2630-2.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The maximum internal spanning tree (MIST) problem is utilized to determine a spanning tree in a graph G, with the maximum number of possible internal vertices. The incremental maximum internal spanning tree (IMIST) problem is the incremental version of MIST whose feasible solutions are edge-sequences e(1), e(2), ..., e(n-1) such that the first k edges form trees for all k is an element of [n - 1]. A solution's quality is measured using with lower being better. Here, opt(G, k) denotes the number of internal vertices in a tree with k edges in G, which has the largest possible number of internal vertices, and |In(T-k)| is the number of internal vertices in the tree comprising the solution's first k edges. We first obtained an IMIST algorithm with a competitive ratio of 2, followed by a 12/7-competitive algorithm based on an approximation algorithm for MIST.
Keywords:
maximum internal spanning tree
incremental problem
approximation algorithm
competitive ratio
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
7.6
Papers:
4.9K
Citations:
8.9K