- Linear Circuit Synthesis using Weighted Steiner Trees
2024/08/07 by Nir Gavrielov, Gavrielov, Nir, Alexander Ivrii +3 · 1 citation
Computer Science · Engineering · Mathematics · #Combinatorics #Computer science #FOS: Physical sciences #Low-power high-performance VLSI design #Mathematics #Quantum Physics (quant-ph) #Steiner tree problem #VLSI and Analog Circuit Testing #VLSI and FPGA Design Techniques
- Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
2021/01/01 by Pavel Dvořák, Andreas E. Feldmann, Dušan Knop +3 · 1 citation
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #VLSI and FPGA Design Techniques #Steiner tree problem #Parameterized complexity #Kernelization #Approximation algorithm #Graph #k-minimum spanning tree #Tree (set theory) #Function (biology) #Time complexity
- Solving Steiner trees: Recent advances, challenges, and perspectives
2020/11/27 by Ivana Ljubić · 1 citation
Engineering · Computer Science · Mathematics · #VLSI and FPGA Design Techniques #Advanced Multi-Objective Optimization Algorithms #Vehicle Routing Optimization Methods #Steiner tree problem #Heuristics #Computer science #Combinatorial optimization #Integer programming #Metaheuristic #Mathematical optimization #Theoretical computer science #Mathematics #Algorithm
- Breaching the 2-Approximation Barrier for Connectivity Augmentation: a Reduction to Steiner Tree
2019/11/06 by Jarosław Byrka, Byrka, Jarosław, Fabrizio Grandoni +3 · 3 citations
Computer Science · Materials Science · Mathematics · #05C85 #68Q25 #68W25 #Advanced Graph Theory Research #Approximation algorithm #Cardinality (data modeling) #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Data Structures and Algorithms (cs.DS) #Discrete mathematics #FOS: Computer and information sciences #Graphene research and applications #Mathematics #Reduction (mathematics) #Set (abstract data type) #Steiner tree problem #Tree (set theory)
- Branched coverings and Steiner ratio
2015/06/12 by Alexander Ivanov, A. A. Tuzhilin · 1 citation
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Advanced Materials and Mechanics #Point processes and geometric inequalities #Isosceles triangle #Steiner tree problem #Combinatorics #Mathematics #Euclidean geometry #Tetrahedron #Vertex (graph theory) #Steiner system #Minimal surface #Euclidean space #Geometry #Graph
- Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
2015/01/01 by Fedor V. Fomin, Petteri Kaski, Daniel Lokshtanov +2 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Exponential function #Graph #Interconnection Networks and Systems #Mathematical analysis #Mathematics #Parameterized complexity #Running time #Space (punctuation) #Steiner tree problem #Time complexity #Tree (set theory) #Vertex (graph theory)
- Experimental Algorithms : 14th International Symposium, SEA 2015, Paris, France, June 29 July 1, 2015, Proceedings
2015/01/01 by Evripidis Bampis · 1 citation
Computer Science · Engineering · Mathematics · #Algorithm #Combinatorial optimization #Computer science #Knapsack problem #Mathematical optimization #Mathematics #Modular Robots and Swarm Intelligence #Optimization and Search Problems #Robotic Mechanisms and Dynamics #Robotic Path Planning Algorithms #Solver #Steiner tree problem #Theoretical computer science #Time complexity
- Steiner Tree Approximation via Iterative Randomized Rounding
2013/02/01 by Jarosław Byrka, Fabrizio Grandoni, Thomas Rothvoß +2 · 23 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Approximation algorithm #Binary tree #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Iterative method #K-ary tree #Linear programming #Linear programming relaxation #Machine Learning and Algorithms #Mathematical optimization #Mathematics #Minimum spanning tree #Randomized rounding #Relaxation (psychology) #Rounding #Sequence (biology) #Steiner tree problem #Tree (set theory) #Tree structure #k-minimum spanning tree
- The increasing cost tree search for optimal multi-agent pathfinding
2012/11/20 by Guni Sharon, Roni Stern, Meir Goldenberg +1 · 13 citations
Computer Science · Mathematics · #AI-based Problem Solving and Planning #Algorithm #Beam search #Computer science #Constraint Satisfaction and Optimization #Mathematical optimization #Mathematics #Pathfinding #Pruning #Robotic Path Planning Algorithms #Search algorithm #Search problem #Search tree #Set (abstract data type) #Shortest path problem #Speedup #State (computer science) #Steiner tree problem #Task (project management) #Theoretical computer science #Tree (set theory)
- Existence and regularity results for the Steiner problem
2012/02/16 by Emanuele Paolini, Eugene Stepanov · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Class (philosophy) #Combinatorics #Compact space #Computational Geometry and Mesh Generation #Computer science #Connection (principal bundle) #Discrete mathematics #Geometry #Hausdorff dimension #Hausdorff measure #Hausdorff space #Mathematics #Measure (data warehouse) #Metric (unit) #Metric space #Pure mathematics #Set (abstract data type) #Space (punctuation) #Steiner tree problem #Topology Optimization in Engineering
- Secret Key Generation for a Pairwise Independent Network Model
2010/07/20 by Sirin Nitinawarat, Nitinawarat, Sirin, Chunxuan Ye +7 · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Mathematics · #Artificial intelligence #Combinatorics #Computer network #Computer science #Computer security #Cooperative Communication and Network Coding #DNA and Biological Computing #Encryption #FOS: Computer and information sciences #Graph #Information Theory (cs.IT) #Key (lock) #Key generation #Mathematics #Multigraph #Pairwise comparison #Secrecy #Shared secret #Steiner tree problem #Theoretical computer science #Tree (set theory) #Upper and lower bounds #Wireless Communication Security Techniques #cs.IT #math.IT
- An improved LP-based approximation for steiner tree
2010/06/05 by Jarosław Byrka, Fabrizio Grandoni, Thomas Rothvoß +1 · 1 citation
Computer Science · Engineering · Mathematics · #Complexity and Algorithms in Graphs #VLSI and FPGA Design Techniques #Advanced Graph Theory Research #Steiner tree problem #Rounding #Combinatorics #k-minimum spanning tree #Approximation algorithm #Mathematics #Linear programming relaxation #Tree (set theory) #Minimum spanning tree #Randomized rounding #Spanning tree #Relaxation (psychology) #Discrete mathematics #Sequence (biology) #Graph #K-ary tree #Mathematical optimization #Tree structure #Computer science #Linear programming #Binary tree
- 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2
2009/01/01 by Piotr Berman, Marek Karpiński, Marek Karpinski +2 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Approximation algorithm #Artificial intelligence #Binary tree #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Enhanced Data Rates for GSM Evolution #Gomory–Hu tree #Graph #K-ary tree #Mathematics #Minimum spanning tree #Spanning tree #Steiner tree problem #Tree (set theory) #Tree structure #VLSI and FPGA Design Techniques #Vertex (graph theory) #Vertex connectivity #k-minimum spanning tree
- Dynamic Programming for Minimum Steiner Trees
2007/10/01 by B. Fuchs, Bernhard Fuchs, Walter Kern +9 · 2 citations
Computer Science · Engineering · Mathematics · #Algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Dynamic programming #Formal Methods in Verification #Mathematical optimization #Mathematics #Order (exchange) #Parameterized complexity #Programming language #Running time #Set (abstract data type) #Steiner tree problem #Tree (set theory) #VLSI and FPGA Design Techniques
- Packing Steiner trees with identical terminal sets
2004/04/13 by Petteri Kaski · 1 citation
Computer Science · Engineering · Mathematics · #Combinatorics #Computer network #Computer science #Discrete mathematics #Interconnection Networks and Systems #Low-power high-performance VLSI design #Mathematics #Steiner tree problem #Terminal (telecommunication) #VLSI and FPGA Design Techniques
- A note on distributed multicast routing in point-to-point networks
2001/10/01 by Roman Novak, Jože Rugelj, Joz̆e Rugelj +1 · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Optical Network Technologies #Algorithm #Computer network #Computer science #Distance Vector Multicast Routing Protocol #Distributed computing #Heuristics #Interconnection Networks and Systems #Mathematical optimization #Mathematics #Multicast #Pragmatic General Multicast #Protocol Independent Multicast #Software-Defined Networks and 5G #Source-specific multicast #Steiner tree problem #Xcast
- Vojtěch Jarnı́k's work in combinatorial optimization
2001/05/01 by Bernhard Korte, Bernhard Körte, Jaroslav Nešetřil · 2 citations
Business, Management and Accounting · Computer Science · Decision Sciences · Mathematics · #Business Strategy and Innovation #Combinatorial analysis #Combinatorial optimization #Combinatorial proof #Combinatorics #Constraint Satisfaction and Optimization #Discrete mathematics #Euclidean geometry #Mathematical optimization #Mathematics #Minimum spanning tree #Operations Management Techniques #Spanning tree #Steiner tree problem #Tree (set theory)
- Approximation Algorithms for Connected Dominating Sets
1998/04/01 by S. Guha, Suvajyoti Guha, S. Khuller +1 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Approximation algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Connected dominating set #Discrete mathematics #Dominating set #Graph #Independent set #Line graph #Mathematics #Maximal independent set #Minimum spanning tree #Pathwidth #Steiner tree problem #Theory of computation #Time complexity #Vertex (graph theory) #Vertex cover
- A General Approximation Technique for Constrained Forest Problems
1995/04/01 by Michel X. Goemans, David P. Williamson · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Optimization and Search Problems #Travelling salesman problem #Steiner tree problem #Approximation algorithm #Mathematics #Combinatorics #Triangle inequality #Shortest path problem #Matching (statistics) #Time complexity #Connection (principal bundle) #Binary logarithm #Covering problems #Discrete mathematics #Mathematical optimization #Graph #Computer science
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
1994/11/01 by Martin Fürer, Balaji Raghavachari · 1 citation
Engineering · Computer Science · Mathematics · #VLSI and FPGA Design Techniques #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Combinatorics #Steiner tree problem #Mathematics #Degree (music) #k-minimum spanning tree #Spanning tree #Minimum spanning tree #Gomory–Hu tree #Minimum degree spanning tree #Graph #Discrete mathematics #Tree (set theory) #Connected dominating set #K-ary tree #Tree structure #Binary tree
- Min cut is NP-complete for edge weighted trees
1988/06/01 by Burkhard Monien, I. Hal Sudborough · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Interconnection Networks and Systems #Combinatorics #Mathematics #Vertex (graph theory) #Feedback vertex set #NP-complete #Completeness (order theory) #Time complexity #Discrete mathematics #Planar #Planar graph #Maximum cut #Steiner tree problem #Graph #Computer science
- A faster approximation algorithm for the Steiner problem in graphs
1986/05/01 by Y. F. Wu, Peter Widmayer, P. Widmayer +2 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Algorithm #Approximation algorithm #Binary tree #Combinatorics #Complexity and Algorithms in Graphs #Connected dominating set #Discrete mathematics #Gomory–Hu tree #Graph #Graph power #K-ary tree #Line graph #Mathematics #Spanning tree #Steiner tree problem #Theory of computation #Tree structure #Undirected graph #VLSI and FPGA Design Techniques #Wheel graph #k-minimum spanning tree
- A NEW BOUND FOR EUCLIDEAN STEINER MINIMAL TREES
1985/05/01 by Fan Chung, F. R. K. Chung, Ron Graham +1 · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Citation #Combinatorics #Computer science #Conjecture #Interconnection Networks and Systems #Library science #Mathematics #Steiner tree problem #Upper and lower bounds #VLSI and FPGA Design Techniques
- The Rectilinear Steiner Tree Problem is NP-Complete
1977/06/01 by M. R. Garey, David S. Johnson · 5 citations
Engineering · Computer Science · Mathematics · #VLSI and FPGA Design Techniques #Interconnection Networks and Systems #Computational Geometry and Mesh Generation #Steiner tree problem #Mathematics #Combinatorics #Heuristics #Tree (set theory) #Discrete mathematics #Graph #Polyomino #Plane (geometry) #Algorithm #Mathematical optimization #Geometry
- On Steiner Minimal Trees with Rectilinear Distance
1976/01/01 by F. K. Hwang · 5 citations
Engineering · Computer Science · Mathematics · #VLSI and FPGA Design Techniques #Interconnection Networks and Systems #Computational Geometry and Mesh Generation #Combinatorics #Steiner tree problem #Mathematics #Tree (set theory) #Plane (geometry) #Cartesian coordinate system #Spanning tree #Discrete mathematics #Geometry
- The Steiner-Lehmus Theorem
1963/01/01 by Gerald Gilbert, G. Gilbert, D. MacDonnell · 1 citation
Mathematics · Medicine · #Algebraic and Geometric Analysis #Calculus (dental) #Combinatorics #Discrete mathematics #History and Theory of Mathematics #Mathematical economics #Mathematics #Medicine #Steiner tree problem
- Analytical researches connected with Steiner’s extension of Malfatti’s problem
1854/12/31 by Arthur Cayley · 1 citation
Mathematics · #History and Theory of Mathematics #Mathematics and Applications #Extension (predicate logic) #Mathematics #Order (exchange) #Combinatorics #Memoir #Surface (topology) #Steiner tree problem #Calculus (dental) #Mathematical economics #Computer science #Geometry #Art history #Art