Method of forming, searching, or generating quasi-minimum tree providing optimum network configuration, and information recording medium which stores program thereof

• US 20030079198A1
• Filed: 03/12/2002
• Published: 04/24/2003
• Est. Priority Date: 10/24/2001
• Status: Abandoned Application

• Current Assignee: Bogenpfeil Co., Ltd.
• Original Assignee: Bogenpfeil Co., Ltd.
• Inventors: Yamamoto, Haruo
• Application Number:
  US10/095,065
• Publication Number:
  US 20030079198A1
• Time in Patent Office: Days
• US Class Current: 716/13
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06F 17/17 Function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method G06F17/18 takes precedence ; interpolation for numerical control G05B19/18
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18

Abstract

A method for forming, searching, or generating a quasi-minimum tree providing an optimum network configuration, which provides an approximate solution to the Steiner problem. This method is a method for forming, searching, or generating a quasi-minimum tree providing an optimum network configuration connecting Steiner points v1 to v5 which are a plurality of vertexes defined by selecting vertexes and edges on an undirected graph which is a geometrical structure consisting of vertexes and weighted edges, wherein, a plurality of trees which do not share said vertexes and edges with one another are created or searched by connecting vertexes to one another beginning from those with which the distance, which provides the total sum of the weights for the edges included in a single path connecting between any two provisional points, is the shortest, while creating or searching a tree providing a path which includes no closed path and is tolerated to be branched; and then, said plurality of trees are connected to one another to provide a tree (a quasi-minimum tree) with which all of said plurality of vertexes defined, v1 to v5, are connected to one another, and the total sum of the weights for said edges included is at a quasi-minimum.

Claims

1. A forming, searching, or generating method for forming, searching, or generating a quasi-minimum tree providing an optimum network configuration connecting Steiner points which are a plurality of vertexes defined by selecting vertexes and edges on an undirected graph which is a geometrical structure consisting of vertexes and weighted edges, wherein,

in creating or searching a path for forming, searching or generating an optimum network configuration by selecting said vertexes and edges,

a plurality of trees which do not share said vertexes and edges with one another are created or searched by connecting vertexes to one another beginning from those with which the distance, which provides the total sum of the weights for the edges included in a single path connecting between any two provisional points, is the shortest, while creating or searching a tree providing a path which includes no closed path and is tolerated to be branched;

and then, said plurality of trees are connected to one another to provide a tree with which all of said plurality of vertexes defined, i.e., Steiner points are connected to one another, and the total sum of the weights for said edges included is at a quasi-minimum.

3. A method of creating, searching, or generating a quasi-minimum tree providing an optimum network configuration as claimed in claim 1 or 2, wherein said method of creating, searching, or generating a quasi-minimum tree providing an optimum network configuration gradually generates or extends said tree by adding said vertexes and edges for connecting the vertexes one by one in sequence, respectively.

4. A method of creating, searching, or generating a quasi-minimum tree providing an optimum network configuration as claimed in any one of claims 1 to 3, wherein said method of forming, searching, or generating a quasi-minimum tree providing an optimum network configuration forms or generates a new tree by connecting said trees to one another.

5. A method of creating, searching, or generating a quasi-minimum tree providing an optimum network configuration as claimed in any one of claims 1 to 4, wherein said method of forming, searching, or generating a quasi-minimum tree providing an optimum network configuration has trees with said plurality of vertexes defined, i.e., Steiner points which number is k as the initial state of starting of forming, searching, or generating a quasi-minimum tree providing an optimum network configuration, and the respective trees are comprised of only one Steiner point which is different from one another.

6. A method of creating, searching, or generating a quasi-minimum tree providing an optimum network configuration as claimed in any one of claims 1 to 5, wherein said method of forming, searching, or generating a quasi-minimum tree providing an optimum network configuration defines the total sum of the weights for the edges which are included in a single path connecting between any two provisional points on said undirected graph as the distance, and computes the distance between points, which is the shortest distance between the vertex and the tree, on said method of forming a quasi-minimum tree providing an optimum network configuration.

7. A method of creating, searching, or generating a quasi-minimum tree providing an optimum network configuration as claimed in any one of claims 1 to 6, wherein said method of forming, searching, or generating a quasi-minimum tree providing an optimum network configuration defines the total sum of the weights for the edges which are included in a single path connecting between any two provisional points, and computes the distance between trees, which is the shortest distance between said trees.

8. A method of creating, searching, or generating a quasi-minimum tree providing an optimum network configuration as claimed in any one of claims 1 to 7, wherein said method of forming, searching, or generating a quasi-minimum tree providing an optimum network configuration selects, in adding vertex to tree, a tree and a vertex to be added to the tree, an edge for connecting the vertex, respectively, on the basis of information about the distance between points, which is the shortest distance between said vertex and tree.

9. A method of creating, searching, or generating a quasi-minimum tree providing an optimum network configuration as claimed in any one of claims 1 to 8, wherein said method of forming, searching, or generating a quasi-minimum tree providing an optimum network configuration selects, in connecting trees to one another, trees to be connected on the basis of the distance between trees, which is the shortest distance between said trees.

10. A method of creating, searching, or generating a quasi-minimum tree providing an optimum network configuration as claimed in any one of claims 1 to 9, wherein said method of forming, searching, or generating a quasi-minimum tree providing an optimum network configuration performs either addition operation for vertex or connection operation for trees on the basis of the comparison of said distance between points with said distance between trees.

11. A method of creating, searching, or generating a quasi-minimum tree providing an optimum network configuration as claimed in any one of claims 1 to 10, wherein said method of forming, searching, or generating a quasi-minimum tree providing an optimum network configuration identifies the tree to which a vertex belongs, and will not connect the vertexes which belong to the same tree, so that no closed path is formed on said undirected graph.

2. A forming, searching, or generating method for forming, searching, or generating a quasi-minimum tree providing an optimum network configuration connecting Steiner points which are a plurality of vertexes defined by selecting vertexes and edges on an undirected graph which is a geometrical structure consisting of vertexes and weighted edges, wherein,

in the course of forming or generating said quasi-minimum tree providing an optimum network configuration,

a plurality of trees providing a path which includes no closed path and is tolerated to be branched are formed and generated at the same time, and the plurality of trees do not share said vertexes and edges with one another.

12. A computer readable information recording medium which is used with a forming, searching, or generating method for forming, searching, or generating a quasi-minimum tree providing an optimum network configuration connecting Steiner points which are a plurality of vertexes defined by selecting vertexes and edges on an undirected graph which is a geometrical structure consisting of vertexes and weighted edges, wherein,

in creating or searching a path for forming, searching or generating an optimum network configuration by selecting said vertexes and edges,

a plurality of trees which do not share said vertexes and edges with one another are created or searched by connecting vertexes to one another beginning from those with which the distance, which provides the total sum of the weights for the edges included in a single path connecting between any two provisional points, is the shortest, while creating or searching a tree providing a path which includes no closed path and is tolerated to be branched;

and then, said plurality of trees are connected to one another to provide a tree with which all of said plurality of vertexes defined, i.e., Steiner points are connected to one another, and the total sum of the weights for said edges included is at a quasi-minimum, wherein

a program for executing said formation, search, or generation of a quasi-minimum tree providing an optimum network configuration is recorded.

14. A computer readable information recording medium which is used with a method of creating, searching, or generating a quasi-minimum tree providing an optimum network configuration as claimed in claim 12 or 13, wherein said method of creating, searching, or generating a quasi-minimum tree providing an optimum network configuration gradually generates or extends said tree by adding said vertexes and edges for connecting the vertexes one by one in sequence, respectively, wherein

a program for executing said formation, search, or generation of a quasi-minimum tree providing an optimum network configuration is recorded.

15. A computer readable information recording medium which is used with a method of creating, searching, or generating a quasi-minimum tree providing an optimum network configuration as claimed in any one of claims 12 to 14, wherein said method of forming, searching, or generating a quasi-minimum tree providing an optimum network configuration forms or generates a new tree by connecting said trees to one another, wherein

a program for executing said formation, search, or generation of a quasi-minimum tree providing an optimum network configuration is recorded.

16. A computer readable information recording medium which is used with a method of creating, searching, or generating a quasi-minimum tree providing an optimum network configuration as claimed in any one of claims 12 to 15, wherein said method of forming, searching, or generating a quasi-minimum tree providing an optimum network configuration has trees with said plurality of vertexes defined, i.e., Steiner points which number is k as the initial state of starting of forming, searching, or generating a quasi-minimum tree providing an optimum network configuration, and the respective trees are comprised of only one Steiner point which is different from one another, wherein

a program for executing said formation, search, or generation of a quasi-minimum tree providing an optimum network configuration is recorded.

17. A computer readable information recording medium which is used with a method of creating, searching, or generating a quasi-minimum tree providing an optimum network configuration as claimed in any one of claims 12 to 16, wherein said method of forming, searching, or generating a quasi-minimum tree providing an optimum network configuration defines the total sum of the weights for the edges which are included in a single path connecting between any two provisional points on said undirected graph as the distance, and computes the distance between points, which is the shortest distance between the vertex and the tree, on said method of forming a quasi-minimum tree providing an optimum network configuration, wherein

a program for executing said formation, search, or generation of a quasi-minimum tree providing an optimum network configuration is recorded.

18. A computer readable information recording medium which is used with a method of creating, searching, or generating a quasi-minimum tree providing an optimum network configuration as claimed in any one of claims 12 to 17, wherein said method of forming, searching, or generating a quasi-minimum tree providing an optimum network configuration defines the total sum of the weights for the edges which are included in a single path connecting between any two provisional points, and computes the distance between trees, which is the shortest distance between said trees, wherein

a program for executing said formation, search, or generation of a quasi-minimum tree providing an optimum network configuration is recorded.

19. A computer readable information recording medium which is used with a method of creating, searching, or generating a quasi-minimum tree providing an optimum network configuration as claimed in any one of claims 12 to 18, wherein said method of forming, searching, or generating a quasi-minimum tree providing an optimum network configuration selects, in adding vertex to tree, a tree and a vertex to be added to the tree, an edge for connecting the vertex, respectively, on the basis of information about the distance between points, which is the shortest distance between said vertex and tree, wherein

a program for executing said formation, search, or generation of a quasi-minimum tree providing an optimum network configuration is recorded.

20. A computer readable information recording medium which is used with a method of creating, searching, or generating a quasi-minimum tree providing an optimum network configuration as claimed in any one of claims 12 to 19, wherein said method of forming, searching, or generating a quasi-minimum tree providing an optimum network configuration selects, in connecting trees to one another, trees to be connected on the basis of the distance between trees, which is the shortest distance between said trees, wherein

a program for executing said formation, search, or generation of a quasi-minimum tree providing an optimum network configuration is recorded.

21. A computer readable information recording medium which is used with a method of creating, searching, or generating a quasi-minimum tree providing an optimum network configuration as claimed in any one of claims 12 to 20, wherein said method of forming, searching, or generating a quasi-minimum tree providing an optimum network configuration performs either addition operation for vertex or connection operation for trees on the basis of the comparison of said distance between points with said distance between trees, wherein

a program for executing said formation, search, or generation of a quasi-minimum tree providing an optimum network configuration is recorded.

22. A computer readable information recording medium which is used with a method of creating, searching, or generating a quasi-minimum tree providing an optimum network configuration as claimed in any one of claims 12 to 21, wherein said method of forming, searching, or generating a quasi-minimum tree providing an optimum network configuration identifies the tree to which a vertex belongs, and will not connect the vertexes which belong to the same tree, so that no closed path is formed on said undirected graph, wherein

a program for executing said formation, search, or generation of a quasi-minimum tree providing an optimum network configuration is recorded.

13. A computer readable information recording medium which is used with a forming, searching, or generating method for forming, searching, or generating a quasi-minimum tree providing an optimum network configuration connecting Steiner points which are a plurality of vertexes defined by selecting vertexes and edges on an undirected graph which is a geometrical structure consisting of vertexes and weighted edges, wherein,

in the course of forming or generating said quasi-minimum tree providing an optimum network configuration,

a plurality of trees providing a path which includes no closed path and is tolerated to be branched are formed and generated at the same time, and the plurality of trees do not share said vertexes and edges with one another, wherein

a program for executing said formation, search, or generation of a quasi-minimum tree providing an optimum network configuration is recorded.

23. A computer readable information recording medium which records a program for creating or searching a path for forming or generating a quasi-minimum tree providing an optimum network configuration connecting Steiner points which are a plurality of vertexes defined by selecting vertexes and edges on an undirected graph which is a geometrical structure consisting of vertexes and weighted edges, wherein,

in creating or searching a path for forming, searching or generating an optimum network configuration by selecting said vertexes and edges,

the program causes the computer to execute processing comprising:

a step for reading or inputting data of said undirected graph;

a step for reading or inputting data of said Steiner points;

a step for creating or searching a plurality of trees which do not share said vertexes and edges with one another by connecting vertexes to one another beginning from those with which the distance, which provides the total sum of the weights for the edges included in a single path connecting between any two provisional points, is the shortest, while creating or searching a tree providing a path which includes no closed path and is tolerated to be branched;

a step for connecting said plurality of trees to one another to provide a tree with which all of said plurality of vertexes defined are connected to one another, and the total sum of the weights for said edges included is at a quasi-minimum; and

a step for outputting the results of said respective steps.