【摘 要】
：
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
【机 构】
：
School of Computer Science and Engineering,Central South University,Changsha 410083,China;Hunan Prov
论文部分内容阅读
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 e1,e2,...,en-1 such that the first k edges form trees for all k ∈[n-1].A solution\'s quality is measured using maxk∈[n-1]opt(G,k)/|In(Tk)| 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(Tk)| 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.
其他文献
In this paper,the steady-state response regimes of nonlinear energy harvesters with a resistor-inductor resonant circuit are theoretically investigated.The complexification averaging (CA) method is used to theoretically analyze the energy harvesting perfo
Based on observation data from urban observation stations in Nanjing and Suzhou at two heights in the roughness sublayer above the canopy and observation data at three heights in the SORPES station at the Xianlin Campus of Nanjing University in a suburban
Radiative cooling can achieve cooling effect without consuming any energy by delivering energy into outer space (3 K) through“atmospheric window” (8-13 μm).Conventional radiative cooling coating with multi-layer structure was severely restricted during ap
This paper proposes a data-driven method using a parametric representation of relative rotations to classify human lower-limb locomotion,which is designed for wearable robots.Three Inertial measurement units(IMUs)are mounted on the subject\'s waist,left
Woodpeckers can withstand a fierce impact during pecking.Previous studies have focused on the biomechanical analysis of the pecking process,the properties of the beak and hyoid bone of woodpecker;however,the biological characteristics of the woodpecker br
The development of Ni-based single crystal superalloys relies heavily on the composition design with the addition of critical alloying elements,e.g.,Re and Ru.Understanding the role of alloying effects require to know the configurations of the alloying el
Dear editor,rnClustering is a fundamental problem in computer science.This problem is to partition a given set of clients into sev-eral clusters such that clients in the same cluster are more similar to each other.In many clustering applications,the clien
Effects of liquid fuel composition variations on characteristics of self-excited thermo-acoustic instabilities in a lean premixed,pre-vaporized gas turbine model combustor were experimentally studied.Test fuels included practical RP-3 jet fuel and its ble
Text generation is a fundamental and important task in natural language processing.Most of the existing models generate text in a sequential manner and have difficulty modeling complex dependency structures.In this paper,we treat the text generation task