发明申请
- 专利标题: Method for finding maximum volume and minimum cut in a network of interconnected nodes
- 专利标题(中): 在互联节点网络中查找最大容量和最小值的方法
-
申请号: US10928627申请日: 2004-08-27
-
公开(公告)号: US20050235236A1公开(公告)日: 2005-10-20
- 发明人: Sunil Sharma , Ajay Tomar , Dhabalendu Samanta
- 申请人: Sunil Sharma , Ajay Tomar , Dhabalendu Samanta
- 申请人地址: IN Uttar Pradesh
- 专利权人: STMicroelectronics Pvt. Ltd.
- 当前专利权人: STMicroelectronics Pvt. Ltd.
- 当前专利权人地址: IN Uttar Pradesh
- 优先权: IN1073/DEL/2003 20030829
- 主分类号: G06F9/45
- IPC分类号: G06F9/45 ; G06F17/50
摘要:
A method for finding a maximum volume and minimum cutset in a network of interconnected nodes is provided. The method is applicable to systems that can be reduced to such a network, including telecommunication networks, traffic networks, computer networks, layouts, hydraulic networks, etc. An equivalent network is derived by replacing all nodes other then the source and sink by two interconnected nodes. A conventional method applies an augmenting path algorithm that identifies a cutset. If the feasible cutset is not achieved then a reduced network is constructed by directly connecting the member nodes of identified cutsets to the source node and repeating the above process for the reduced network until a feasible cutset is achieved.
公开/授权文献
信息查询