- Plane Triangulations Without Spanning 2-Trees
2022/03/19 by Allan Bickle, Bickle, Allan · 1 citation
Computer Science · Mathematics · #05C10 #Advanced Graph Theory Research #Combinatorics #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete mathematics #FOS: Mathematics #Graph #Line graph #Mathematics #Minimum spanning tree #Pathwidth #Planar graph #Spanning tree #Trémaux tree #Vertex (graph theory) #math.CO #msc:05C10
- An improved LP-based approximation for steiner tree
2010/06/05 by Jarosław Byrka, Fabrizio Grandoni, Thomas Rothvoß +1 · 5 citations
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
- Approximation Algorithms for Connected Dominating Sets
1998/04/01 by S. Guha, Suvajyoti Guha, Samir Khuller +1 · 9 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 randomized linear-time algorithm to find minimum spanning trees
1995/03/01 by David R. Karger, Philip N. Klein, Robert E. Tarjan · 31 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Combinatorics #Computer science #Data Management and Algorithms #Data Mining Algorithms and Applications #Distributed minimum spanning tree #Euclidean minimum spanning tree #Graph #Kruskal's algorithm #Mathematics #Minimum spanning tree #Prim's algorithm #Randomized algorithm #Reverse-delete algorithm #Spanning tree #Time complexity
- Choosing a Spanning Tree for the Integer Lattice Uniformly
1991/10/01 by Robin Pemantle · 15 citations
Mathematics · #Stochastic processes and statistical mechanics #Mathematical Dynamics and Fractals #Limits and Structures in Graph Theory #Spanning tree #Mathematics #Combinatorics #Minimum degree spanning tree #Euclidean minimum spanning tree #Minimum spanning tree #Limiting #Integer lattice #Lattice (music) #Discrete mathematics #Connected dominating set #Tree (set theory)
- A linear-time algorithm for finding a minimum spanning pseudoforest
1988/04/01 by Harold N. Gabow, Robert E. Tarjan · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics #Connected dominating set #Connectivity #Discrete mathematics #Graph #Interconnection Networks and Systems #Kruskal's algorithm #Mathematics #Minimum degree spanning tree #Minimum spanning tree #Reverse-delete algorithm #Spanning tree #Time complexity #VLSI and FPGA Design Techniques
- Scaling and related techniques for geometry problems
1984/01/01 by Harold N. Gabow, Jon Bentley, Robert E. Tarjan · 12 citations
Computer Science · Mathematics · #Data Management and Algorithms #Computational Geometry and Mesh Generation #Algorithms and Data Compression #Rectangle #Scaling #Maxima #Computational geometry #Cartesian coordinate system #Minimum spanning tree #Combinatorics #Tree (set theory) #Mathematics #Space (punctuation) #Geometry #Algorithm #Computer science #Discrete mathematics
- Finding Minimum Spanning Trees
1976/12/01 by David R. Cheriton, Robert E. Tarjan · 8 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Combinatorics #Spanning tree #Minimum spanning tree #Mathematics #Binary logarithm #Omega #Upper and lower bounds #k-minimum spanning tree #Discrete mathematics #Tree structure #Binary tree #K-ary tree #Physics
- Priority queues with update and finding minimum spanning trees
1975/12/01 by D. Barton Johnson, Donald B. Johnson · 6 citations
Business, Management and Accounting · Computer Science · Engineering · Mathematics · #Advanced Queuing Theory Analysis #Algorithm #Combinatorics #Computer science #Mathematics #Minimum degree spanning tree #Minimum spanning tree #Optimization and Packing Problems #Optimization and Search Problems #Parallel computing #Programming language #Queue #Spanning tree