1. One or more processor-accessible tangible media comprising processor-executable instructions for network analysis with Steiner trees, wherein the processor-executable instructions, when executed, direct a system to perform acts comprising: receiving data specifying a network; accepting Steiner tree parameters; creating a Steiner tree model on the data specifying the network responsive to the Steiner tree parameters, the Steiner tree model including a local representation having a depth constraint for neighborhood vertices, the depth constraint ensuring that a depth of any given vertex is one more than a depth of another vertex to which the given vertex points; and analyzing the data specifying the network to ascertain a Steiner tree solution based on the Steiner tree model that includes the local representation and using a locally-oriented combinatorial algorithm; the act of analyzing including one or more acts of passing messages, which relate to at least one depth, between and among neighborhood vertices.