Method and apparatus for generating n-segment steiner trees

A computer program product comprising:

• a computer usable medium having computer readable program code embodied therein for generating a Steiner tree connecting at least two points comprising:
• computer readable program code configured to cause a computer to generate a Boolean network function representing a network of interconnects, each interconnect having as an end point one of said at least two points;
• computer readable program code configured to cause a computer to determine a binary decision diagram for said Boolean network function;
• and
• computer readable program code configured to cause a computer to determine a solution for said Steiner tree by determining solution values for one or more of said variables of said Boolean network function.

A computer system comprising:

• a processor;
• a system for generating a Steiner tree connecting at least two points comprising:
• a Boolean function generator for generating a Boolean network function representing a network of interconnects connecting said points to be connected;
• a binary decision diagram generator for generating a binary decision diagram of said Boolean network function;
• and
• a solution generator for generating a Steiner tree solution based on a solution of said Boolean network function as determined from said binary decision diagram.

A system for generating a Steiner tree for connecting at least two points comprising:

• means for generating a Bollean network function representing a network of interconnects, each interconnect having as an end point one of said at least two points;
• means for determining a binary decision diagram for said Boolean network function;
• and
• means for determining a solution for said Steiner tree by determining solution values for said Boolean network function from said binary decision diagram.