The presence of circles in the network maximum flow problem increases the complexity of the preflow algorithm.This study proposes a novel two-stage preflow algorithm to address this issue.First,this study proves that ...The presence of circles in the network maximum flow problem increases the complexity of the preflow algorithm.This study proposes a novel two-stage preflow algorithm to address this issue.First,this study proves that at least one zero-flow arc must be present when the flow of the network reaches its maximum value.This result indicates that the maximum flow of the network will remain constant if a zero-flow arc within a circle is removed;therefore,the maximum flow of each network without circles can be calculated.The first stage involves identifying the zero-flow arc in the circle when the network flow reaches its maximum.The second stage aims to remove the zero-flow arc identified and modified in the first stage,thereby producing a new network without circles.The maximum flow of the original looped network can be obtained by solving the maximum flow of the newly generated acyclic network.Finally,an example is provided to demonstrate the validity and feasibility of this algorithm.This algorithm not only improves computational efficiency but also provides new perspectives and tools for solving similar network optimization problems.展开更多
Maximum Flow Problem (MFP) discusses the maximum amount of flow that can be sent from the source to sink. Edmonds-Karp algorithm is the modified version of Ford-Fulkerson algorithm to solve the MFP. This paper present...Maximum Flow Problem (MFP) discusses the maximum amount of flow that can be sent from the source to sink. Edmonds-Karp algorithm is the modified version of Ford-Fulkerson algorithm to solve the MFP. This paper presents some modifications of Edmonds-Karp algorithm for solving MFP. Solution of MFP has also been illustrated by using the proposed algorithm to justify the usefulness of proposed method.展开更多
This work presents the hydrologic estimations of the hydraulic underground arched culvert channel (UACC) in Sabinal Basin, Chiapas, México and the hydrological problems associated with it, such as the erosion phe...This work presents the hydrologic estimations of the hydraulic underground arched culvert channel (UACC) in Sabinal Basin, Chiapas, México and the hydrological problems associated with it, such as the erosion phenomenon and abrasion cavity formation in it. On the other hand, the maximum flows that the UACC could transport were analyzed, concluding that it no longer has the hydraulic capacity to transport the flow rate associated to return periods equal to or greater than five years and that maximum permissible velocity UACC’s bottom is 3 m/s.展开更多
Calculating the most reliable maximum flow(MRMF)from the edge cache node to the requesting node can provide an important reference for selecting the best edge cache node in a content delivery network(CDN).However,SDBA...Calculating the most reliable maximum flow(MRMF)from the edge cache node to the requesting node can provide an important reference for selecting the best edge cache node in a content delivery network(CDN).However,SDBA,as the current state-of-the-art MRMF algorithm,is too complex to meet real-time computing needs.This paper proposes a set of MRMF algorithms:NWCD(Negative Weight Community Deletion),SCPDAT(Single-Cycle Preference Deletion Approximation algorithm with Time constraint)and SCPDAP(Single-Cycle Preference Deletion Approximation algorithm with Probability constraint).NWCD draws on the“flow-shifting”algorithm of minimum cost and maximum flow,and further defines the concept of negative weight community.This algorithm continuously deletes the negative weight communities,which can increase reliability while keeping the flow constant in the residual graph.It is proven that when all negative weight communities are deleted,the corresponding maximum flow is the MRMF.SCPDAT tries to approach the optimal solution to the greatest extent possible within the limited time,while SCPDAP tries to reach the probability threshold in the shortest amount of time.Both of these adopt the strategy of first deleting single-cycle communities(which contribute more to the reliability with lower time cost).Experiments show that,compared with SDBA,NWCD combined with the probabilistic pruning achieves an order of magnitude improvement in time cost,while SCPDAT and SCPDAP demonstrate better time performance and increased applicability.展开更多
Deep space networks,satellite networks,ad hoc networks,and the Internet can be modeled as DTNs(Delay Tolerant Networks).As a fundamental problem,the maximum flow problem is of vital importance for routing and service ...Deep space networks,satellite networks,ad hoc networks,and the Internet can be modeled as DTNs(Delay Tolerant Networks).As a fundamental problem,the maximum flow problem is of vital importance for routing and service scheduling in networks.However,there exists no permanent end-to-end path since the topology and the characteristics of links are time-variant,resulting in a crucial maximum flow problem in DTNs.In this paper,we focus on the single-source-single-sink maximum flow problem of buffer-limited DTNs,followed by a valid algorithm to solve it.First,the BTAG(Buffer-limited Time Aggregated Graph)is constructed for modeling the buffer-limited DTN.Then,on the basis of BTAG,the two-way cache transfer series and the relevant transfer rules are designed,and thus a BTAG-based maximum flow algorithm is proposed to solve the maximum flow problem in buffer-limited DTNs.Finally,a numerical example is given to demonstrate the effectiveness of the proposed algorithm.展开更多
The idea of the inverse optimization problem is to adjust the values of the parameters so that the observed feasible solutions are indeed optimal.The modification cost is measured by different norms,such asl1,l2,l∞no...The idea of the inverse optimization problem is to adjust the values of the parameters so that the observed feasible solutions are indeed optimal.The modification cost is measured by different norms,such asl1,l2,l∞norms and the Hamming distance,and the goal is to adjust the parameters as little as possible.In this paper,we consider the inverse maximum flow problem under the combination of the weighted l2 norm and the weighted Hamming distance,i.e.,the modification cost is fixed in a given interval and depends on the modification out of the given interval.We present a combinatorial algorithm which can be finished in O(nm)to solve it due to the minimum cut of the residual network.展开更多
The velocity dip phenomenon may occur in a part of or in the whole flow field of open channel flows due to the secondary flow effect. Based on rectangular flume experiments and the laser Doppler velocimetry, the influ...The velocity dip phenomenon may occur in a part of or in the whole flow field of open channel flows due to the secondary flow effect. Based on rectangular flume experiments and the laser Doppler velocimetry, the influence of the distance to the sidewall and the aspect ratio on the velocity dip is investigated. Through application of statistical methods to the experimental results, it is proposed that the flow field may be divided into two regions, the relatively strong sidewall region and the relatively weak sidewall region. In the former region, the distance to the sidewall greatly affects the location of maximum velocity, and, in the latter region, both the distance to the sidewall and the aspect ratio influence the location of the maximum velocity.展开更多
Summary:Changes of maximum expiratory flow at 25%and 50%of vital capacity(MEF2s and MEFso,respectively),and predominant parameters indicating small airways function in asthmatics before and after bronchodilator(BD)rev...Summary:Changes of maximum expiratory flow at 25%and 50%of vital capacity(MEF2s and MEFso,respectively),and predominant parameters indicating small airways function in asthmatics before and after bronchodilator(BD)reversibility test have been less interpreted.Our study aimed to investigate the clinical role of changes of MEF2s and MEFso before and after BD reversibility test in diagnosing asthma.Forced expiratory volume in the first second(FEV),MEF2s,and MEFso were measured before and after BD reversibility test in 207 asthmatic patients using standard process.Forty healthy individuals were enrolled as controls.Receiver operating characteristic(ROC)curve was used to assess the diagnostic accuracy of reversibility of MEF2s and MEFgo before and after BD reversibility test(OMEF 2s%and AMEF so%,respectively)in diagnosing asthma.Among these functional criteria,AMEF2;%and 0MEFs%≥25%performed the best diagnostic performance.The sensitivity,specificity,and accuracy of AMEF 25%≥25%as an objcctive diagnostic test for asthma were 63.29%,87.50%,and 67.21%,and of AMEFs0%≥25%were 79.23%,85.00%,and 80.16%,respectively.The area under the ROC curve of the indicators was 0.8203 and 0.9104,respectively.By contrast,an increase in FEV≥12%and 200 mL demonstrated a sensitivity of 62.32%,specificity of 82.50%,and accuracy of 65.59%in diagnosing asthma.The changes of MEF2s and MEFso before and after BD reversibility test may be of additional value in the clinical diagnosis of asthma,with cutoff values of 25%being the most.展开更多
极端灾害将导致电力系统与通信系统同时发生大面积瘫痪,基于“保电救灾、通信先行”原则,优先恢复故障通信是支撑保障电力系统安全运行的关键。该文针对灾后电力通信高效恢复问题,提出了一种计及电力侧状态感知需求与运行调控能力保障...极端灾害将导致电力系统与通信系统同时发生大面积瘫痪,基于“保电救灾、通信先行”原则,优先恢复故障通信是支撑保障电力系统安全运行的关键。该文针对灾后电力通信高效恢复问题,提出了一种计及电力侧状态感知需求与运行调控能力保障的增广路径最大流电力通信网络恢复算法。首先考虑到电力通信系统与电力物理系统的紧耦合特性,设计了计及电力侧影响的状态感知与运行调控能力量化指标,辨识关键信息节点。然后,通过图论最大流理论,搜寻关键信息节点的增广路径集。在此基础上,引入恢复贡献度,从增广路径集中选择具有大容量、低延时以及少故障链路的通信路径进行优先重建,为灾后电力系统快速恢复过程提供可达、可靠的通信支撑。最后,以IEEE39标准系统作为仿真算例,验证了所提恢复策略下的通信系统具有更高的通信服务质量(quality of service,QoS),避免了在恢复过程中由于带宽容量不足而发生业务频繁掉线风险。展开更多
This paper investigates the maximum network through- put for resource-constrained space networks based on the delay and disruption-tolerant networking （DTN） architecture. Specifically, this paper proposes a methodol...This paper investigates the maximum network through- put for resource-constrained space networks based on the delay and disruption-tolerant networking （DTN） architecture. Specifically, this paper proposes a methodology for calculating the maximum network throughput of multiple transmission tasks under storage and delay constraints over a space network. A mixed-integer linear programming （MILP） is formulated to solve this problem. Simula- tions results show that the proposed methodology can successfully calculate the optimal throughput of a space network under storage and delay constraints, as well as a clear, monotonic relationship between end-to-end delay and the maximum network throughput under storage constraints. At the same time, the optimization re- sults shine light on the routing and transport protocol design in space communication, which can be used to obtain the optimal network throughput.展开更多
基金The National Natural Science Foundation of China(No.72001107,72271120)the Fundamental Research Funds for the Central Universities(No.NS2024047,NP2024106)the China Postdoctoral Science Foundation(No.2020T130297,2019M660119).
文摘The presence of circles in the network maximum flow problem increases the complexity of the preflow algorithm.This study proposes a novel two-stage preflow algorithm to address this issue.First,this study proves that at least one zero-flow arc must be present when the flow of the network reaches its maximum value.This result indicates that the maximum flow of the network will remain constant if a zero-flow arc within a circle is removed;therefore,the maximum flow of each network without circles can be calculated.The first stage involves identifying the zero-flow arc in the circle when the network flow reaches its maximum.The second stage aims to remove the zero-flow arc identified and modified in the first stage,thereby producing a new network without circles.The maximum flow of the original looped network can be obtained by solving the maximum flow of the newly generated acyclic network.Finally,an example is provided to demonstrate the validity and feasibility of this algorithm.This algorithm not only improves computational efficiency but also provides new perspectives and tools for solving similar network optimization problems.
文摘Maximum Flow Problem (MFP) discusses the maximum amount of flow that can be sent from the source to sink. Edmonds-Karp algorithm is the modified version of Ford-Fulkerson algorithm to solve the MFP. This paper presents some modifications of Edmonds-Karp algorithm for solving MFP. Solution of MFP has also been illustrated by using the proposed algorithm to justify the usefulness of proposed method.
文摘This work presents the hydrologic estimations of the hydraulic underground arched culvert channel (UACC) in Sabinal Basin, Chiapas, México and the hydrological problems associated with it, such as the erosion phenomenon and abrasion cavity formation in it. On the other hand, the maximum flows that the UACC could transport were analyzed, concluding that it no longer has the hydraulic capacity to transport the flow rate associated to return periods equal to or greater than five years and that maximum permissible velocity UACC’s bottom is 3 m/s.
基金partly supported by Open Research Fund from State Key Laboratory of Smart Grid Protection and Control,China(Zhang B,www.byqsc.net/com/nrjt/),Rapid Support Project(61406190120,Zhang B)the Fundamental Research Funds for the Central Universities(2242021k10011,Zhang B,www.seu.edu.cn)the National Key R&D Program of China(2018YFC0830200,Zhang B,www.most.gov.cn).
文摘Calculating the most reliable maximum flow(MRMF)from the edge cache node to the requesting node can provide an important reference for selecting the best edge cache node in a content delivery network(CDN).However,SDBA,as the current state-of-the-art MRMF algorithm,is too complex to meet real-time computing needs.This paper proposes a set of MRMF algorithms:NWCD(Negative Weight Community Deletion),SCPDAT(Single-Cycle Preference Deletion Approximation algorithm with Time constraint)and SCPDAP(Single-Cycle Preference Deletion Approximation algorithm with Probability constraint).NWCD draws on the“flow-shifting”algorithm of minimum cost and maximum flow,and further defines the concept of negative weight community.This algorithm continuously deletes the negative weight communities,which can increase reliability while keeping the flow constant in the residual graph.It is proven that when all negative weight communities are deleted,the corresponding maximum flow is the MRMF.SCPDAT tries to approach the optimal solution to the greatest extent possible within the limited time,while SCPDAP tries to reach the probability threshold in the shortest amount of time.Both of these adopt the strategy of first deleting single-cycle communities(which contribute more to the reliability with lower time cost).Experiments show that,compared with SDBA,NWCD combined with the probabilistic pruning achieves an order of magnitude improvement in time cost,while SCPDAT and SCPDAP demonstrate better time performance and increased applicability.
基金supported by the National Science Foundation(Nos.91338115,61231008)National S&T Major Project(No.2015ZX03002006)+2 种基金the Fundamental Research Funds for the Central Universities(Nos.WRYB142208,JB140117)Shanghai Aerospace Science and Technology Innovation Fund(No.201454)the 111 Project(No.B08038).
文摘Deep space networks,satellite networks,ad hoc networks,and the Internet can be modeled as DTNs(Delay Tolerant Networks).As a fundamental problem,the maximum flow problem is of vital importance for routing and service scheduling in networks.However,there exists no permanent end-to-end path since the topology and the characteristics of links are time-variant,resulting in a crucial maximum flow problem in DTNs.In this paper,we focus on the single-source-single-sink maximum flow problem of buffer-limited DTNs,followed by a valid algorithm to solve it.First,the BTAG(Buffer-limited Time Aggregated Graph)is constructed for modeling the buffer-limited DTN.Then,on the basis of BTAG,the two-way cache transfer series and the relevant transfer rules are designed,and thus a BTAG-based maximum flow algorithm is proposed to solve the maximum flow problem in buffer-limited DTNs.Finally,a numerical example is given to demonstrate the effectiveness of the proposed algorithm.
基金This research is supported by the Fundamental Research Funds for the Central Universities(No.20720190068)the China Scholarship Council(No.201706315073).
文摘The idea of the inverse optimization problem is to adjust the values of the parameters so that the observed feasible solutions are indeed optimal.The modification cost is measured by different norms,such asl1,l2,l∞norms and the Hamming distance,and the goal is to adjust the parameters as little as possible.In this paper,we consider the inverse maximum flow problem under the combination of the weighted l2 norm and the weighted Hamming distance,i.e.,the modification cost is fixed in a given interval and depends on the modification out of the given interval.We present a combinatorial algorithm which can be finished in O(nm)to solve it due to the minimum cut of the residual network.
基金supported by the National Natural Science Foundation of China (Grants No.50879019,50909036,and 50879020)the Research Fund for the Doctoral Program of Higher Education (Grants No.200802940001 and 200802941028)+3 种基金the Fundamental Research Funds for the Central Universities (Grants No.2010B02214,2009B08014,and 2010B14214)the Natural Science Foundation of Hohai University(Grant No. 2008426411)the Jiangsu "333" Program for High Level Talents (Grant No. 2017-B08038)the National Undergraduate Innovation Training Plan (Grant No.G20101106)
文摘The velocity dip phenomenon may occur in a part of or in the whole flow field of open channel flows due to the secondary flow effect. Based on rectangular flume experiments and the laser Doppler velocimetry, the influence of the distance to the sidewall and the aspect ratio on the velocity dip is investigated. Through application of statistical methods to the experimental results, it is proposed that the flow field may be divided into two regions, the relatively strong sidewall region and the relatively weak sidewall region. In the former region, the distance to the sidewall greatly affects the location of maximum velocity, and, in the latter region, both the distance to the sidewall and the aspect ratio influence the location of the maximum velocity.
基金This project was supported by the National Natural Science Foundation of China(No.81970024)partly by Scientific Research Project of Wuhan Health Committee(No.WX16C45).
文摘Summary:Changes of maximum expiratory flow at 25%and 50%of vital capacity(MEF2s and MEFso,respectively),and predominant parameters indicating small airways function in asthmatics before and after bronchodilator(BD)reversibility test have been less interpreted.Our study aimed to investigate the clinical role of changes of MEF2s and MEFso before and after BD reversibility test in diagnosing asthma.Forced expiratory volume in the first second(FEV),MEF2s,and MEFso were measured before and after BD reversibility test in 207 asthmatic patients using standard process.Forty healthy individuals were enrolled as controls.Receiver operating characteristic(ROC)curve was used to assess the diagnostic accuracy of reversibility of MEF2s and MEFgo before and after BD reversibility test(OMEF 2s%and AMEF so%,respectively)in diagnosing asthma.Among these functional criteria,AMEF2;%and 0MEFs%≥25%performed the best diagnostic performance.The sensitivity,specificity,and accuracy of AMEF 25%≥25%as an objcctive diagnostic test for asthma were 63.29%,87.50%,and 67.21%,and of AMEFs0%≥25%were 79.23%,85.00%,and 80.16%,respectively.The area under the ROC curve of the indicators was 0.8203 and 0.9104,respectively.By contrast,an increase in FEV≥12%and 200 mL demonstrated a sensitivity of 62.32%,specificity of 82.50%,and accuracy of 65.59%in diagnosing asthma.The changes of MEF2s and MEFso before and after BD reversibility test may be of additional value in the clinical diagnosis of asthma,with cutoff values of 25%being the most.
文摘极端灾害将导致电力系统与通信系统同时发生大面积瘫痪,基于“保电救灾、通信先行”原则,优先恢复故障通信是支撑保障电力系统安全运行的关键。该文针对灾后电力通信高效恢复问题,提出了一种计及电力侧状态感知需求与运行调控能力保障的增广路径最大流电力通信网络恢复算法。首先考虑到电力通信系统与电力物理系统的紧耦合特性,设计了计及电力侧影响的状态感知与运行调控能力量化指标,辨识关键信息节点。然后,通过图论最大流理论,搜寻关键信息节点的增广路径集。在此基础上,引入恢复贡献度,从增广路径集中选择具有大容量、低延时以及少故障链路的通信路径进行优先重建,为灾后电力系统快速恢复过程提供可达、可靠的通信支撑。最后,以IEEE39标准系统作为仿真算例,验证了所提恢复策略下的通信系统具有更高的通信服务质量(quality of service,QoS),避免了在恢复过程中由于带宽容量不足而发生业务频繁掉线风险。
基金supported by the National Natural Sciences Foundation of China(6113200261321061+3 种基金6123101161201183)the National Basic Research Program of China(2014CB340206)the Tsinghua University Initiative Scientific Research Program(2011Z05117)
文摘This paper investigates the maximum network through- put for resource-constrained space networks based on the delay and disruption-tolerant networking （DTN） architecture. Specifically, this paper proposes a methodology for calculating the maximum network throughput of multiple transmission tasks under storage and delay constraints over a space network. A mixed-integer linear programming （MILP） is formulated to solve this problem. Simula- tions results show that the proposed methodology can successfully calculate the optimal throughput of a space network under storage and delay constraints, as well as a clear, monotonic relationship between end-to-end delay and the maximum network throughput under storage constraints. At the same time, the optimization re- sults shine light on the routing and transport protocol design in space communication, which can be used to obtain the optimal network throughput.
