Invention Grant
US07188328B2 Method for finding maximum volume and minimum cut in a network of interconnected nodes
有权
在互联节点网络中查找最大容量和最小值的方法
- Patent Title: Method for finding maximum volume and minimum cut in a network of interconnected nodes
- Patent Title (中): 在互联节点网络中查找最大容量和最小值的方法
-
Application No.: US10928627Application Date: 2004-08-27
-
Publication No.: US07188328B2Publication Date: 2007-03-06
- Inventor: Sunil Kumar Sharma , Ajay Tomar , Dhabalendu Samanta
- Applicant: Sunil Kumar Sharma , Ajay Tomar , Dhabalendu Samanta
- Applicant Address: IN Uttar Pradesh
- Assignee: STMicroelectronics Pvt Ltd.
- Current Assignee: STMicroelectronics Pvt Ltd.
- Current Assignee Address: IN Uttar Pradesh
- Agency: Allen, Dyer, Doppelt, Milbrath & Gilchrist, P.A.
- Agent Lisa K. Jorgenson
- Priority: IN1073/Del/2003 20030829
- Main IPC: G06F17/50
- IPC: G06F17/50

Abstract:
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.
Public/Granted literature
- US20050235236A1 Method for finding maximum volume and minimum cut in a network of interconnected nodes Public/Granted day:2005-10-20
Information query