Aiming at the deficiencies presented by the traditional methods of highway project investment evaluation, the proposed highway investment evaluation method was based on system dynamics. First, we constructed an evaluation index system from profitability, solvency, and risk resistance and clarified the positive and negative causality within the investment evaluation system of highway projects; second, we determined the boundaries of the system dynamics model and divided it into six sub-systems, namely, income, cash flow, investment evaluation, profit, cost, investment and financing, and liabilities; and then, we established the system dynamics model of highway investment evaluation based on the sub-systems. The model made up for the limitations of the traditional discounted cash flow method; finally, taking the China's Yunnan Province an Expressway project as an example, using VENSIM software simulation, we get the evaluation results of the system dynamics model and make a comparative analysis with the discounted cash flow method, which showed that the calculation inaccuracies of the NPV and other financial indicators were in a reasonable range, and the evaluation method had strong operability and practicability. The system dynamics investment evaluation model provided a systematic, intuitive, whole-process investment evaluation method, which provided a theoretical basis for the analysis and decision-making of the investment effect of highway projects.
Citation: Yonghua Liu, Hao Deng, Hanqi Gao, Wei Ni. Research on investment evaluation of highway projects based on system dynamics model[J]. AIMS Mathematics, 2024, 9(8): 20326-20349. doi: 10.3934/math.2024989
Related Papers:
[1]
Anum Iftikhar, Hongbo Shi, Saddam Hussain, Ather Qayyum, M. El-Morshedy, Sanaa Al-Marzouki .
Estimation of finite population mean in presence of maximum and minimum values under systematic sampling scheme. AIMS Mathematics, 2022, 7(6): 9825-9834.
doi: 10.3934/math.2022547
[2]
Khazan Sher, Muhammad Ameeq, Muhammad Muneeb Hassan, Basem A. Alkhaleel, Sidra Naz, Olyan Albalawi .
Novel efficient estimators of finite population mean in stratified random sampling with application. AIMS Mathematics, 2025, 10(3): 5495-5531.
doi: 10.3934/math.2025254
[3]
Jairo A. Angel, Francisco M.M. Rocha, Jorge I. Vélez, Julio M. Singer .
A new test for detecting specification errors in Gaussian linear mixed-effects models. AIMS Mathematics, 2024, 9(11): 30710-30727.
doi: 10.3934/math.20241483
[4]
S. P. Arun, M. R. Irshad, R. Maya, Amer I. Al-Omari, Shokrya S. Alshqaq .
Parameter estimation in the Farlie–Gumbel–Morgenstern bivariate Bilal distribution via multistage ranked set sampling. AIMS Mathematics, 2025, 10(2): 2083-2097.
doi: 10.3934/math.2025098
[5]
Jagdev Singh, Jitendra Kumar, Devendra Kumar, Dumitru Baleanu .
A reliable numerical algorithm for fractional Lienard equation arising in oscillating circuits. AIMS Mathematics, 2024, 9(7): 19557-19568.
doi: 10.3934/math.2024954
[6]
Yasir Hassan, Muhammad Ismai, Will Murray, Muhammad Qaiser Shahbaz .
Efficient estimation combining exponential and ln functions under two phase sampling. AIMS Mathematics, 2020, 5(6): 7605-7623.
doi: 10.3934/math.2020486
[7]
Bowen Tang, Xiaoying Yang, Lin Su .
Shape reconstruction of acoustic obstacle with linear sampling method and neural network. AIMS Mathematics, 2024, 9(6): 13607-13623.
doi: 10.3934/math.2024664
[8]
Xiaofeng Guo, Jianyu Pan .
Approximate inverse preconditioners for linear systems arising from spatial balanced fractional diffusion equations. AIMS Mathematics, 2023, 8(7): 17284-17306.
doi: 10.3934/math.2023884
[9]
Nasrullah Khan, Gadde Srinivasa Rao, Rehan Ahmad Khan Sherwani, Ali Hussein AL-Marshadi, Muhammad Aslam .
Uncertainty-based sampling plans for various statistical distributions. AIMS Mathematics, 2023, 8(6): 14558-14571.
doi: 10.3934/math.2023744
[10]
Jinliang Wang, Fang Wang, Songbo Hu .
On asymptotic correlation coefficient for some order statistics. AIMS Mathematics, 2023, 8(3): 6763-6776.
doi: 10.3934/math.2023344
Abstract
Aiming at the deficiencies presented by the traditional methods of highway project investment evaluation, the proposed highway investment evaluation method was based on system dynamics. First, we constructed an evaluation index system from profitability, solvency, and risk resistance and clarified the positive and negative causality within the investment evaluation system of highway projects; second, we determined the boundaries of the system dynamics model and divided it into six sub-systems, namely, income, cash flow, investment evaluation, profit, cost, investment and financing, and liabilities; and then, we established the system dynamics model of highway investment evaluation based on the sub-systems. The model made up for the limitations of the traditional discounted cash flow method; finally, taking the China's Yunnan Province an Expressway project as an example, using VENSIM software simulation, we get the evaluation results of the system dynamics model and make a comparative analysis with the discounted cash flow method, which showed that the calculation inaccuracies of the NPV and other financial indicators were in a reasonable range, and the evaluation method had strong operability and practicability. The system dynamics investment evaluation model provided a systematic, intuitive, whole-process investment evaluation method, which provided a theoretical basis for the analysis and decision-making of the investment effect of highway projects.
1.
Introduction
We consider only simple and undirected labeled graphs and follow the terminology and notation of [5]. Let G=(V,E) be a graph and v be a vertex of G, we write NG(v) to denote the (open) neighborhood of v. The closed neighborhood of v is defined as NG[v]=NG(v)∪{v}. The degree of v is defined as dG(v)=|NG(v)|. For U⊆V, we write G[U] to denote the subgraph induced by U. The subgraph G[V∖U] is denoted by G−U. Furthermore, G−U can be written by G−u if U={u}.
In a graph G, an independent set is a subset of vertices spanning no edges. Finding an independent set of maximum cardinality in a graph is a widely studied well-known problem of graph theory and is called the maximum independent set problem. In 1982, Hammer et al. [11] studied the maximum independent problem from different perspectives and investigated the vertices contained in all or in no maximum independent sets of a graph. Since then, researchers have extensively studied this kind of problem for some other vertex subsets with given properties. For example, Mynhardt [15], Cockayne et al. [10], and Blidia et al. [3] considered this kind of problem for minimum dominating sets, total dominating sets, and minimum double dominating sets of trees, respectively. Recently, Bouquet et al. [6] studied this kind of problem of minimum dominating sets on claw-free graphs, chordal graphs, and triangle-free graphs.
In a graph G, a dissociation set is a subset of vertices F such that the induced subgraph G[F] has maximum degree at most 1. A maximum dissociation set of G is a dissociation set of maximum cardinality. The dissociation numberψ(G) of a graph G is the cardinality of a maximum dissociation set of G. The concept of dissociation set was introduced by Yannakakis [21] in 1981 and is a natural generalization of independent set. The maximum dissociation set problem, to find a maximum dissociation set in a graph is NP-hard for many subclasses of graphs such as K1,4-free bipartite graphs, C4-free bipartite graphs with vertex degree at most 3, planar graphs with vertex degree at most 4, triangle-free graphs, line graphs, etc. (see [2,4,16,17]). On the other hand, the problem is polynomially solvable for chordal and weakly chordal graphs, circular-arc graphs, AT-free graphs, (chair, K3)-free graphs, etc. (see [8,16]). In terms of exact algorithms, Kardoš, Katrenič and Schiermeyer [13] gave an O∗(1.5171n)-time exact algorithm for the problem in an n-vertex graph. Chang et al. [9] improved the result to O∗(1.4658n). Xiao and Kou [20] proposed an exact algorithm which can solve the problem in O∗(1.4656n) time and polynomial space or O∗(1.3659n) time and exponential space. Computing the dissociation number can be helpful in finding a lower bound for the 1-improper chromatic number of a graph [12]. And the maximum dissociation set problem has applications in telecommunications, scheduling, wireless sensor networks and networking security [1,7].
A k-path vertex cover in a graph G is a subset of vertices intersecting every k-path of G, where a k-path is a path of order k. It is easy to see that a set S of vertices of a graph G is a 3-path vertex cover of G if and only if its complement V(G)∖S is a dissociation set of G. In this decade, the problem of finding a minimum k-path vertex cover in a graph has received great attention [7,13,14,19,20].
The main purpose of this paper is to characterize the vertices contained in all maximum dissociation sets and in no maximum dissociation set of a tree. Define the vertex subsets A(G), F(G) and N(G) by
A(G)={v∈V(G):v is in all maximum dissociation sets of G},F(G)={v∈V(G):v is in some but not all maximum dissociation sets of G},N(G)={v∈V(G):v is in no maximum dissociation set of G}.
On the other hand, the study is also inspired by the relationship between the characteristic of vertex subsets A(G) and N(G) and the number of maximum dissociation sets in a graph G. In [18], Tu, Zhang and Shi found four structure theorems concerning the vertex subsets A(T) and N(T) for a tree T and determined the maximum number of maximum dissociation sets in a tree of order n.
The paper is organized as follows. In Section 2, we introduce some necessary notation and lemmas. In Section 3, we characterize the vertex subsets A(T) and N(T) of a tree T. In Section 4, a linear recognition algorithm which can determine whether a given vertex in a tree is contained in all (or no) maximum dissociation sets of the tree will be presented. Thus, using the recognition algorithm, all vertices contained in all (or no) maximum dissociation sets of a tree of order n can be found in O(n2) time.
2.
Preliminary results
A rooted tree T is a connected acyclic graph with a specified vertex r, called the root of T. Let T be a tree rooted at r and v be a vertex of T, each vertex on the path from the root r to the vertex v, including the vertex v itself, is called an ancestor of v, and a descendant of v is a vertex u such that v is an ancestor of u. An ancestor or descendant of a vertex is proper if it is not the vertex itself. The parentp(v) of v is the immediate proper ancestor of v, a child of v is a vertex u such that p(u)=v. Define the vertex subsets CT(v), DT(v), and DT[v] by
CT(v)={u∈V(T):u is a child of v},
DT(v)={u∈V(T):u is a proper descendant of v},
DT[v]=D(v)∪{v}.
If no confusion occurs, these also be written by C(v), D(v), and D[v], respectively. We write Tv to denote the subtree induced by DT[v].
A leaf in a tree is a vertex with degree 1, a branch vertex is a vertex with degree at least 3. We write B(T) to denote the set of branch vertices of T. A path P in T is called a v−L path, if P joins v to a leaf that is a descendant of v. Denote the order of P by n(P), and for i=0,1,2, define
Ci(v)={u∈C(v):Tu contains a u−L path P with n(P)≡imod3}
Now, some basic observations about maximum dissociation sets of the path are given.
Observation 2.1.Let Pn=u1u2⋯un be a path of order n≥3.
(a) ψ(Pn)=2n+i3, where n≡i(mod3), i=0,1,2.
(b) If n≡0(mod3), then there exists a maximum dissociation set of Pn that contains exactly one leaf.
(c) If n≡1(mod3), then both leaves of Pn belong to all maximum dissociation sets of Pn, furthermore, Pn has a maximum dissociation set F such that dPn[F](u1)=0.
(d) If n≡2(mod3), then there is only one maximum dissociation set F in Pn, furthermore, {u1,un}⊂F and dPn[F](u1)=dPn[F](un)=1.
Proof. (a) Since a maximum dissociation set of Pn contains at most two vertices of three consecutive vertices of Pn, one can easily check the truth of the statement by case analysis.
(b) If n≡0(mod3), then F=V(Pn)∖{u3i,1≤i≤n3} is a maximum dissociation set of Pn that contains exactly one leaf.
(c) If n≡1(mod3), then ψ(Pn)=2n+13. Suppose for a contradiction that there exists a maximum dissociation set in Pn that contains at most one leaf. Then ψ(Pn)=ψ(Pn−1)=2(n−1)3<2n+13, a contradiction. Thus both leaves of Pn belong to all maximum dissociation sets of Pn.
Furthermore, F=V(Pn)∖{u3i+2,0≤i≤n−43} is a maximum dissociation set of Pn such that dPn[F](u1)=0.
(d) If n≡2(mod3), then ψ(Pn)=2n+23. Let F be any maximum dissociation set of Pn. If u1∉F, then ψ(Pn)=ψ(Pn−1)=2(n−1)+13<2n+23, a contradiction. If dPn[F](u1)=0, then ψ(Pn)=ψ(Pn−2)+1=2(n−2)3+1=2n−13<2n+23, a contradiction. Thus, dPn[F](u1)=1. Similarly, dPn[F](un)=1. Since a maximum dissociation set of Pn contains at most two vertices of three consecutive vertices of Pn, one can easily check that there is only one maximum dissociation set in Pn.
Firstly, we characterize A(T) and N(T) in the case where B(T)≤1.
Lemma 2.2.Let T be a rooted tree with the root v. If for each u∈V(T)∖{v}, dT(u)≤2, then
Proof. Because Tw is a path for each w∈C(v), it is easy to determine ψ(Tw) and Ci(v)∩Cj(v)=∅ for i≠j. Note that ∑w∈C(v)ψ(Tw)≤ψ(T)≤∑w∈C(v)ψ(Tw)+1. We consider the two cases.
Case 1.|C2(v)|=0 and |C1(v)|≤1.
If w∈C0(v), then Tw≅Pn with n≡0(mod3). Let Fw be a maximum dissociation set of Tw such that w∉Fw (Fw exists by Observation 2.1(b)). If w∈C1(v), then Tw≅Pn with n≡1(mod3) and let Fw be a maximum dissociation set of Tw such that dTw[Fw](w)=0 (Fw exists by Observation 2.1(c)). Now, let
F=⋃w∈C(v)Fw∪{v},
(2.1)
then F is a dissociation set of T and |F|=∑w∈C(v)ψ(Tw)+1. Thus, F is a maximum dissociation set of T and ψ(T)=∑w∈C(v)ψ(Tw)+1.
Case 2.|C2(v)|≥1 or |C1(v)|≥2.
Suppose for a contradiction that ψ(T)=∑w∈C(v)ψ(Tw)+1. Let F be a maximum dissociation set of T. Then, v∈F and F∩Tw is a maximum dissociation set of Tw for each w∈C(v). Let Fw:=F∩Tw for each w∈C(v). If w∈C2(v), then Tw≅Pn with n≡2(mod3). By Observation 2.1(d), w∈Fw and dTw[Fw](w)=1. Thus, if |C2(v)|≥1, there is a 3-path in T[F] that contains the vertex v, a contradiction.
If w∈C1(v), then Tw≅Pn with n≡1(mod3). By Observation 2.1(c), we have w∈Fw. Thus, if |C1(v)|≥2, then there is a 3-path in T[F] that contains the vertex v, a contradiction.
The proof is complete.
Theorem 2.3.Let T be a rooted tree with the root v. If for each u∈V(T)∖{v}, dT(u)≤2, then
(a) v∈A(T) if and only if |C2(v)|=0 and |C1(v)|≤1;
(b) v∈N(T) if and only if |C2(v)|=2 or |C1(v)|+|C2(v)|≥3.
Proof. (a) Necessity. Suppose for a contradiction that |C2(v)|≥1 or |C1(v)|≥2 and v∈A(T). Let F=⋃w∈C(v)Fw, where Fw is a maximum dissociation set of Tw for each w∈C(v). By Lemma 2.2, we have ψ(T)=∑w∈C(v)ψ(Tw). Thus, F is a maximum dissociation set of T and v∉F, which contradicts with v∈A(T).
Sufficiency. Suppose that |C2(v)|=0 and |C1(v)|≤1. Then ψ(T)=∑w∈C(v)ψ(Tw)+1 by Lemma 2.2 and the vertex v is in all maximum dissociation sets of T. Thus, v∈A(T).
The proof of (a) is complete.
(b) Necessity. Suppose for a contradiction that |C2(v)|≠2 and |C1(v)|+|C2(v)|≤2 and v∈N(T).
If |C2(v)|=0 and |C1(v)|≤1, then v∈A(T) by (a), a contradiction.
If |C2(v)|=0 and |C1(v)|=2, then we assume w1,w2∈C1(v). For each w∈C0(v), there exists a maximum dissociation set Fw of Tw such that w∉Fw by Observation 2.1(b). For w1∈C1(v), we have Tw1−w1≅Pn with n≡0(mod3). Let Fw1 be a maximum dissociation set of Tw1−w1. Then |Fw1|=ψ(Tw1)−1 by Observation 2.1(a). For w2∈C1(v), there exists a maximum dissociation set Fw2 of Tw2 such that dTw2[Fw2](w2)=0 by Observation 2.1(c). Let F=⋃w∈C0(v)Fw∪Fw1∪Fw2∪{v}, then F is a dissociation set of T and |F|=∑w∈C(v)ψ(Tw). By Lemma 2.2, F is a maximum dissociation set of T and v∈F, a contradiction.
If |C2(v)|=1 and |C1(v)|≤1, then we assume w3∈C2(v). For w3∈C2(v), we have Tw3−w3≅Pn with n≡1(mod3). Let Fw3 be a maximum dissociation set of Tw3−w3, then |Fw3|=ψ(Tw3)−1 by Observation 2.1(a). For each w∈C0(v), let Fw be a maximum dissociation set of Tw such that w∉Fw. For w∈C1(v), let Fw be a maximum dissociation set of Tw such that dTw[Fw](w)=0. Now let F=⋃w∈C(v)−{w3}Fw∪Fw3∪{v}, then F is a dissociation set of T and |F|=∑w∈C(v)ψ(Tw). By Lemma 2.2, F is a maximum dissociation set of T and v∈F, a contradiction.
Sufficiency. Suppose for a contradiction that |C2(v)|=2 or |C1(v)|+|C2(v)|≥3, and v∉N(T). Let F be a maximum dissociation set of T such that v∈F. For each w∈C0(v), |F∩Tw|≤ψ(Tw). If w∈C2(v), then Tw≅Pn with n≡2(mod3). Since v∈F, we have |F∩Tw|≤ψ(Tw)−1. If w∈C1(v), then every maximum dissociation set Fw of Tw contains the vertex w. Since v∈F, there are at least |C1(v)|−1 vertices w in C1(v) such that |F∩Tw|≤ψ(Tw)−1. Hence, it is easy to check |F|<∑w∈C(v)ψ(Tw)≤ψ(T), a contradiction.
The proof of (b) is complete.
3.
Characterizations of A(T) and N(T)
A technique called pruning process was introduced in [15]. Using the technique and Theorem 2.3, we can characterize A(T) and N(T) for an arbitrary tree T.
Let T be a rooted tree with the root v and u be a branch vertex of T at maximum distance from v. It is easy to see that |C(u)|≥2 and dT(x)≤2 for each x∈D(u). If u≠v, we execute the following pruning process:
● if |C2(u)|≥1 or |C1(u)|≥2, then delete D[u],
● if |C2(u)|=0 and |C1(u)|≤1, then for all w∈C(u)∖{z}, delete D[w], where z is the vertex in C1(u) if |C1(u)|=1, otherwise z is any one vertex in C(u).
This step of pruning process is called a pruning of T at u. Repeat the above pruning process, finally, we obtain a unique tree ˉT called the pruning of T such that dˉT(u)≤2 for each u∈V(ˉT)∖{v}. We will show that the root v is in all maximum dissociation sets (or in no maximum dissociation set) of T if and only if it is in all maximum dissociation sets (or in no maximum dissociation set) of the pruning ˉT of T.
Lemma 3.1.Let T be a rooted tree with the root v and ˉT be the pruning of T. For every maximum dissociation set ˉF of ˉT, there exists a maximum dissociation set F of T such that v∈F if and only if v∈ˉF. Conversely, for every maximum dissociation set F of T, there exists a maximum dissociation set ˉF of ˉT such that v∈ˉF if and only if v∈F.
Proof. We prove the lemma by induction on |B′(T)|, where B′(T)={u∈V(T)∖{v}:d(u)≥3}. If |B′(T)|=0, then T=ˉT and the result holds clearly. Suppose that when |B′(T)|<k, the lemma holds. Let T be a tree with |B′(T)|=k and u be a vertex of B′(T) at maximum distance from v. Let T′ be the tree obtained from T by applying a pruning of T at u. Thus, ˉT is also the pruning of T′.
First, we show that for every maximum dissociation set ˉF of ˉT, there exists a maximum dissociation set F of T such that v∈F if and only if v∈ˉF. By the induction hypothesis, for every maximum dissociation set ˉF of ˉT, there exists a maximum dissociation set F′ of T′ such that v∈F′ if and only if v∈ˉF.
We consider the following two cases.
Case 1.|C2(u)|=0 and |C1(u)|≤1.
For each w∈C(u)∖{z}, Tw≅Pn with n≡0(mod3). Let Fw be a maximum dissociation set of Tw such that w∉Fw (Fw exists by Observation 2.1(b)). Let F=⋃w∈C(u)∖{z}Fw∪F′. Clearly, F is a maximum dissociation set of T. Since v∈F′ if and only if v∈F, we have v∈F if and only if v∈ˉF.
Case 2.|C2(u)|≥1 or |C1(u)|≥2.
In this case, T′=T−D[u]. For each w∈C(u), let Fw be a maximum dissociation set of Tw. Let F=⋃w∈C(u)Fw∪F′. Since |C2(u)|≥1 or |C1(u)|≥2, by Lemma 2.2, ψ(Tu)=∑w∈C(u)ψ(Tw)=∑w∈C(u)|Fw|, which implies that ⋃w∈C(u)Fw is a maximum dissociation set of Tu. Thus, F is a maximum dissociation set of T. Since v∈F′ if and only if v∈F, we have v∈F if and only if v∈ˉF.
Now, we show that for every maximum dissociation set F of T, there exists a maximum dissociation set ˉF of ˉT such that v∈ˉF if and only if v∈F. Likewise, we consider the following two cases.
Case 1.|C2(u)|=0 and |C1(u)|≤1.
For each w∈C(u)∖{z}, we have Tw≅Pn with n≡0(mod3). Let Fw be a maximum dissociation set of Tw such that w∉Fw (Fw exists by Observation 2.1(b)).
For every maximum dissociation set F of T, let F′=F−⋃w∈C(u)∖{z}D[w]. Then F′ is a dissociation set of T′ and v∈F if and only if v∈F′. We will prove that F′ is a maximum dissociation set of T′. Suppose for a contradiction that F1 is a maximum dissociation set of T′ with |F1|>|F′|. Let F2=⋃w∈C(u)∖{z}Fw∪F1. Then F2 is a dissociation set of T and
which contradicts the fact that F is a maximum dissociation set of T. Thus F′ is a maximum dissociation set of T′. By the induction hypothesis, there exists a maximum dissociation set ˉF of ˉT such that v∈F′ if and only if v∈ˉF. Hence, there exists a maximum dissociation set ˉF of ˉT such that v∈F if and only if v∈ˉF.
Case 2.|C2(u)|≥1 or |C1(u)|≥2.
For each w∈C(u), let Fw be a maximum dissociation set of Tw. By Lemma 2.2, ψ(Tu)=∑w∈C(u)ψ(Tw)=∑w∈C(u)|Fw|.
For every maximum dissociation set F of T, let F′=F−D[u]. We will prove that F′ is a maximum dissociation set of T′. Suppose for a contradiction that F1 is a maximum dissociation set of T′ with |F1|>|F′|. Let F2=⋃w∈C(u)Fw∪F1. Then F2 is a dissociation set of T and
|F2|=|F1|+∑w∈C(u)|Fw|>|F′|+|F∩D[u]|=|F|,
(3.2)
which contradicts the fact that F is a maximum dissociation set of T. Thus F′ is a maximum dissociation set of T′. By the induction hypothesis, there exists a maximum dissociation set ˉF of ˉT such that v∈F′ if and only if v∈ˉF. Thus, there exists a maximum dissociation set ˉF of ˉT such that v∈F if and only if v∈ˉF.
We complete the proof.
By Lemma 3.1, we can obtain the following corollary.
Corollary 3.2.Let T be a rooted tree with the root v and ˉT be the pruning of T, then v∈A(T) (or N(T)) if and only if v∈A(ˉT) (or N(ˉT)).
By Theorem 2.3 and Corollary 3.2, the characterizations of A(T) and N(T) can be obtained immediately.
Theorem 3.3.Let T be a tree and v be a vertex of T. Let Tv be the rooted tree obtained from T with the root v and ¯Tv be the pruning of Tv. Then
(a) v∈A(T) if and only if |C2¯Tv(v)|=0 and |C1¯Tv(v)|≤1;
(b) v∈N(T) if and only if |C2¯Tv(v)|=2 or |C1¯Tv(v)|+|C2¯Tv(v)|≥3.
4.
A recognition algorithm
In [7], the authors presented an algorithm which can find a minimum k-path vertex cover in a tree in linear time, it follows that the problem of finding a maximum dissociation set of a tree can be solved in linear time. Let T be a tree and v a vertex of T. The equality ψ(T−v)=ψ(T)−1 holds if and only if v belongs to all maximum dissociation sets of T. Thus the algorithm presented in [7] can be used to determine whether a given vertex in a tree belongs to all maximum dissociation sets of the tree. But, if ψ(T−v)=ψ(T), then it may be that v belongs to no maximum dissociation set of T, it may be that v belongs to some maximum dissociation sets but not all. Hence, the algorithm presented in [7] cannot be used to determine whether a given vertex in a tree belongs to no maximum dissociation set of the tree.
In this section, we present a linear time recognition algorithm which can determine whether a given vertex in a tree is in all maximum dissociation sets, or in some maximum dissociation sets but not all, or in no maximum dissociation set. See Table 1.
Table 1.
A recognition algorithm.
Input: a tree T and a vertex v∈T.
Output: v∈A(T); or v∈F(T); or v∈N(T).
1. change the tree T into a rooted tree by choosing the vertex v as the root
2. compute the distance d(v,u) from v to each other vertex u
3. let B=B(T)∖{v}, where B(T) is the set of branch vertices of T
4. whileB≠∅do
4.1. choose a vertex u in B such that d(v,u) is maximum
4.2. if|C2(u)|≥1 or |C1(u)|≥2, then
T←T−D[u] and B←B∖{u}
4.3. else if|C1(u)|=1, then
T←T−⋃w∈C(u)∖{z}D[w] and B←B∖{u}, where z is the vertex in C1(u)
For a rooted tree, we can use the breadth-first search algorithm to find the distance from the root to each other vertex in linear time. Step 4 is the pruning process of the rooted tree T. The cardinality of the set B is at most |V(T)| and will decrease by 1 after each loop execution. More precisely, let u be a vertex in B such that d(u,v) is maximum and w be a child of u, there exists only one w−L path that joins w to a leaf that is a descendant of v and the order of the w−L path can be obtained from the distances from the root to the vertex w and the leaf. Thus, we can compute the sets C2(u) and C1(u) in O(d(u)) time. The total runtime of Step 4 is O(∑u∈Bd(u)), which implies that Step 4 can be executed in linear time. Thus, the runtime of the recognition algorithm is linear. Using the recognition algorithm we can find all vertices contained in all (or no) maximum dissociation sets of a tree of order n in O(n2) time.
5.
Conclusions
In this paper, we study the maximum dissociation set problem from different perspectives and characterize the vertices belonging to all maximum dissociation sets, and no maximum dissociation set of a tree. Based on the characterization, we present a linear time recognition algorithm which can determine whether a given vertex in a tree is in all maximum dissociation sets, or in some maximum dissociation sets but not all, or in no maximum dissociation set. Thus for a tree with n vertices, we can find all vertices belonging to all (or no) maximum dissociation sets of the tree in O(n2) time.
Acknowledgments
The work is supported by Research Foundation for Advanced Talents of Beijing Technology and Business University (No. 19008021187). We would like to thank two anonymous referees for their many helpful suggestions and comments.
Conflict of interest
The authors declare that they have no competing interests.
References
[1]
Ministry of Transportation and Communications of the People's Republic of China, National Toll Road Statistics Bulletin 2020, 2021.
[2]
Editorial Board of China Journal of Highway, Review of Academic Research on Transportation Engineering in China 2016, China J. Highway, 29 (2016), 1−161.
[3]
H. Huang, Discussion of the national toll road statistical bulletin from a financial perspective, Financ. Account., 2019, 77−78.
[4]
Y. H. Liu, R. K. Duan, K. Shen, Q. X. Luan, H. Q. Gao, H. Deng, An investigation into the determinants of satisfaction concerning varied toll policies on highways using the random forest model, AIMS Math., 9 (2024), 4161−4177. https://doi.org/10.3934/math.2024204 doi: 10.3934/math.2024204
[5]
T. Machiels, T. Compernolle, T. Coppens, Real option applications in megaproject planning: Trends, relevance and research gaps: A literature review, Eur. Plan. Stud., 29 (2021), 446−467. https://doi.org/10.1080/09654313.2020.1742665 doi: 10.1080/09654313.2020.1742665
[6]
X. Y. Cai, G. G. Zhou, Option value analysis of revenue adjustment in operation period of toll road PPP project, Transp. Syst. Eng. Inform., 17 (2017), 7−11.
[7]
Y. Wang, L. Ma, J. Bai, Evaluation of financial risk control of large-scale international projects based on neural network, J. Tongji Univ. (Nat. Sci. Edit.), 43 (2015), 1104−1110.
[8]
L. Li, An empirical study on the rational selection of comprehensive line solution diagram and calculation period for economic evaluation of construction projects, Pract. Underst. Math., 49 (2019), 9−16.
[9]
X. Liu, R. X. Zhou, Y. Zhan, Research on project investment evaluation index based on interval number, J. Beijing Univ. Chem. Technol. (Nat. Sci. Edit.), 44 (2017), 124−127.
[10]
S. P. Shepherd, A review of system dynamics models applied in transportation, Transportmetrica B, 2 (2014), 83−105. https://doi.org/10.1080/21680566.2014.916236 doi: 10.1080/21680566.2014.916236
[11]
Q. N. Liu, Y. W. Wang, M. L. Yao, J. Li, Research on the evolution and simulation of operational risk of PPP project based on system dynamics, J. Eng. Manag., 31 (2017), 57−61.
[12]
Z. Y. Zhao, S. Fan, T. Dai, Application of system dynamics model for value-for-money evaluation of PPP projects, J. Huaqiao Univ. (Nat. Sci. Edit.), 41 (2020), 765−771.
[13]
C. C. Xue, J. K. Zhou, System dynamics modeling and analysis of PPP project performance–A highway as an example, Financ. Account. Mon., 2019,171−176.
[14]
W. Xu, J. J. Liu, J. M. Li, H. Wang, Q. T. Xiao, A novel hybrid intelligent model for molten iron temperature forecasting based on machine learning, AIMS Math., 9 (2024), 1227−1247. https://doi.org/10.3934/math.2024061 doi: 10.3934/math.2024061
[15]
F. L. Feng, N. Yu, Research on pack back transportation tariff based on system dynamics and logit model, J. Railway Sci. Eng., 15 (2018), 2980−2987.
[16]
P. D. Chao, L. Y. Zhou, Y. F. Kang, Simulation analysis of transportation restructuring policy based on system dynamics, Railway Transp. Econ., 46 (2024), 78−89.
[17]
Z. W. Wang, Z. Y. Xiang, X. Liu, Research on urban traffic congestion management strategy based on system dynamics model, J. Changsha Univ. Technol. (Nat. Sci. Edit.), 19 (2022), 81−88.
[18]
R. Pokharel, E. J. Miller, K. Chapple, Modeling car dependency and policies towards sustainable mobility: A system dynamics approach, Transport. Res. Part D-Tr. E., 125 (2023), 103978. https://doi.org/10.1016/j.trd.2023.103978 doi: 10.1016/j.trd.2023.103978
[19]
X. F. Lai, Z. X. Chen, X. Wang, C. H. Chiu, Risk propagation and mitigation mechanisms of disruption and trade risks for a global production network, Transport. Res. E-Log., 170 (2023), 103013. https://doi.org/10.1016/j.tre.2022.103013 doi: 10.1016/j.tre.2022.103013
[20]
Institute of Standards and Quotas, Ministry of Housing and Urban-Rural Development, Institute of Planning and Research, Ministry of Transportation, Methods and parameters of economic evaluation of highway construction projects, China Planning Press, 2010.
[21]
Yunnan Province construction cost consulting service standards, T/YNECA 001-2018.
This article has been cited by:
1.
Muhammad Azeem, Sheetal Kalyani,
A modified version of diagonal systematic sampling in the presence of linear trend,
2022,
17,
1932-6203,
e0265179,
10.1371/journal.pone.0265179
2.
Muhammad Azeem, Sundus Hussain, Musarrat Ijaz, Najma Salahuddin, Abdul Salam,
An improved version of systematic sampling design for use with linear trend data,
2023,
9,
24058440,
e17121,
10.1016/j.heliyon.2023.e17121
Yonghua Liu, Hao Deng, Hanqi Gao, Wei Ni. Research on investment evaluation of highway projects based on system dynamics model[J]. AIMS Mathematics, 2024, 9(8): 20326-20349. doi: 10.3934/math.2024989
Yonghua Liu, Hao Deng, Hanqi Gao, Wei Ni. Research on investment evaluation of highway projects based on system dynamics model[J]. AIMS Mathematics, 2024, 9(8): 20326-20349. doi: 10.3934/math.2024989