Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Steiner_tree_problem> ?p ?o }
- Steiner_tree_problem abstract "The Steiner tree problem, or the minimum Steiner tree problem, named after Jakob Steiner, is a problem in combinatorial optimization, which may be formulated in a number of settings, with the common part being that it is required to find the shortest interconnect for a given set of objects.The Steiner tree problem is superficially similar to the minimum spanning tree problem: given a set V of points (vertices), interconnect them by a network (graph) of shortest length, where the length is the sum of the lengths of all edges. The difference between the Steiner tree problem and the minimum spanning tree problem is that, in the Steiner tree problem, extra intermediate vertices and edges may be added to the graph in order to reduce the length of the spanning tree. These new vertices introduced to decrease the total length of connection are known as Steiner points or Steiner vertices. It has been proved that the resulting connection is a tree, known as the Steiner tree. There may be several Steiner trees for a given set of initial vertices.The Steiner tree problem has applications in circuit layout or network design. Most versions of the Steiner tree problem are NP-complete. In fact, one of these was among Karp's original 21 NP-complete problems. Some restricted cases can be solved in polynomial time. In practice, heuristics are used.".
- Steiner_tree_problem thumbnail Steiner_3_points.svg?width=300.
- Steiner_tree_problem wikiPageExternalLink aptsver.html.
- Steiner_tree_problem wikiPageExternalLink phylomurka.sf.net.
- Steiner_tree_problem wikiPageExternalLink steinerkompendium.
- Steiner_tree_problem wikiPageExternalLink implement.shtml.
- Steiner_tree_problem wikiPageExternalLink RonaldLG1988.
- Steiner_tree_problem wikiPageExternalLink watch?v=PI6rAOWu-Og.
- Steiner_tree_problem wikiPageID "498304".
- Steiner_tree_problem wikiPageLength "16864".
- Steiner_tree_problem wikiPageOutDegree "59".
- Steiner_tree_problem wikiPageRevisionID "681743616".
- Steiner_tree_problem wikiPageWikiLink APX.
- Steiner_tree_problem wikiPageWikiLink APX-complete.
- Steiner_tree_problem wikiPageWikiLink Annals_of_Discrete_Mathematics.
- Steiner_tree_problem wikiPageWikiLink Approximation_algorithm.
- Steiner_tree_problem wikiPageWikiLink CRC_Press.
- Steiner_tree_problem wikiPageWikiLink Category:Computational_problems_in_graph_theory.
- Steiner_tree_problem wikiPageWikiLink Category:Geometric_algorithms.
- Steiner_tree_problem wikiPageWikiLink Category:Geometric_graphs.
- Steiner_tree_problem wikiPageWikiLink Category:NP-complete_problems.
- Steiner_tree_problem wikiPageWikiLink Category:Trees_(graph_theory).
- Steiner_tree_problem wikiPageWikiLink Combinatorial_optimization.
- Steiner_tree_problem wikiPageWikiLink Complete_graph.
- Steiner_tree_problem wikiPageWikiLink Computational_complexity_theory.
- Steiner_tree_problem wikiPageWikiLink Decision_problem.
- Steiner_tree_problem wikiPageWikiLink Degree_(graph_theory).
- Steiner_tree_problem wikiPageWikiLink Electrical_network.
- Steiner_tree_problem wikiPageWikiLink Electronic_design_automation.
- Steiner_tree_problem wikiPageWikiLink Elsevier.
- Steiner_tree_problem wikiPageWikiLink Euclidean_distance.
- Steiner_tree_problem wikiPageWikiLink Fermat_point.
- Steiner_tree_problem wikiPageWikiLink Glossary_of_graph_theory.
- Steiner_tree_problem wikiPageWikiLink Graph_(mathematics).
- Steiner_tree_problem wikiPageWikiLink Heuristic.
- Steiner_tree_problem wikiPageWikiLink Heuristics.
- Steiner_tree_problem wikiPageWikiLink Infimum_and_supremum.
- Steiner_tree_problem wikiPageWikiLink Jakob_Steiner.
- Steiner_tree_problem wikiPageWikiLink K-edge-connected_graph.
- Steiner_tree_problem wikiPageWikiLink K-vertex-connected_graph.
- Steiner_tree_problem wikiPageWikiLink Karps_21_NP-complete_problems.
- Steiner_tree_problem wikiPageWikiLink Line_segment.
- Steiner_tree_problem wikiPageWikiLink Metric_space.
- Steiner_tree_problem wikiPageWikiLink Minimum_spanning_tree.
- Steiner_tree_problem wikiPageWikiLink NP-complete.
- Steiner_tree_problem wikiPageWikiLink NP-completeness.
- Steiner_tree_problem wikiPageWikiLink NP-hard.
- Steiner_tree_problem wikiPageWikiLink NP-hardness.
- Steiner_tree_problem wikiPageWikiLink Network_design.
- Steiner_tree_problem wikiPageWikiLink Network_planning_and_design.
- Steiner_tree_problem wikiPageWikiLink North-Holland.
- Steiner_tree_problem wikiPageWikiLink North_Holland.
- Steiner_tree_problem wikiPageWikiLink Opaque_forest_problem.
- Steiner_tree_problem wikiPageWikiLink Optimization_problem.
- Steiner_tree_problem wikiPageWikiLink Physical_design_(electronics).
- Steiner_tree_problem wikiPageWikiLink Plane_(geometry).
- Steiner_tree_problem wikiPageWikiLink Point_(geometry).
- Steiner_tree_problem wikiPageWikiLink Polynomial-time_algorithm.
- Steiner_tree_problem wikiPageWikiLink Polynomial-time_approximation_scheme.
- Steiner_tree_problem wikiPageWikiLink Polynomial_time.
- Steiner_tree_problem wikiPageWikiLink Projective_plane.
- Steiner_tree_problem wikiPageWikiLink Quasi-bipartite_graph.
- Steiner_tree_problem wikiPageWikiLink Rectilinear_distance.
- Steiner_tree_problem wikiPageWikiLink Routing_(electronic_design_automation).
- Steiner_tree_problem wikiPageWikiLink Springer_Science+Business_Media.
- Steiner_tree_problem wikiPageWikiLink Steiner_point.
- Steiner_tree_problem wikiPageWikiLink Steiner_points.
- Steiner_tree_problem wikiPageWikiLink Supremum.
- Steiner_tree_problem wikiPageWikiLink Taxicab_geometry.
- Steiner_tree_problem wikiPageWikiLink Time_complexity.
- Steiner_tree_problem wikiPageWikiLink Tree_(graph_theory).
- Steiner_tree_problem wikiPageWikiLink Triangle_inequality.
- Steiner_tree_problem wikiPageWikiLink VLSI_circuit.
- Steiner_tree_problem wikiPageWikiLink Very-large-scale_integration.
- Steiner_tree_problem wikiPageWikiLink Weighted_graph.
- Steiner_tree_problem wikiPageWikiLink Wire_routing.
- Steiner_tree_problem wikiPageWikiLink World_Scientific.
- Steiner_tree_problem wikiPageWikiLink File:Steiner_3_points.svg.
- Steiner_tree_problem wikiPageWikiLink File:Steiner_4_points.svg.
- Steiner_tree_problem wikiPageWikiLinkText "Steiner Tree Problems".
- Steiner_tree_problem wikiPageWikiLinkText "Steiner point".
- Steiner_tree_problem wikiPageWikiLinkText "Steiner tree problem".
- Steiner_tree_problem wikiPageWikiLinkText "Steiner tree problem#Euclidean Steiner tree".
- Steiner_tree_problem wikiPageWikiLinkText "Steiner tree problem#Metric Steiner tree".
- Steiner_tree_problem wikiPageWikiLinkText "Steiner tree problem#Steiner ratio".
- Steiner_tree_problem wikiPageWikiLinkText "Steiner trees".
- Steiner_tree_problem wikiPageWikiLinkText "minimum Steiner tree".
- Steiner_tree_problem first "M.".
- Steiner_tree_problem hasPhotoCollection Steiner_tree_problem.
- Steiner_tree_problem id "s/s110270".
- Steiner_tree_problem last "Hazewinkel".
- Steiner_tree_problem title "Steiner tree problem".
- Steiner_tree_problem wikiPageUsesTemplate Template:Cite_book.
- Steiner_tree_problem wikiPageUsesTemplate Template:Cite_journal.
- Steiner_tree_problem wikiPageUsesTemplate Template:Commons_category.
- Steiner_tree_problem wikiPageUsesTemplate Template:Garey-Johnson.
- Steiner_tree_problem wikiPageUsesTemplate Template:Main.
- Steiner_tree_problem wikiPageUsesTemplate Template:Springer.
- Steiner_tree_problem wikiPageUsesTemplate Template:Use_dmy_dates.
- Steiner_tree_problem subject Category:Computational_problems_in_graph_theory.