- An introduction to graph theory
2023/08/02 by Darij Grinberg, Grinberg, Darij · 2 voices
Computer Science · Mathematics · #Advanced Graph Theory Research #Bipartite graph #Combinatorics #Discrete mathematics #Eulerian path #Graph #Graph theory #Hamiltonian path #Lagrangian #Matching (statistics) #Mathematics #Pure mathematics #Spanning tree #math.CO #math.HO
- Efficient Subgraph Matching
2019/06/18 by Myoungji Han, Hyunjoon Kim, Geonmo Gu +2 · 1 citation
Computer Science · Mathematics · #Graph Theory and Algorithms #Advanced Graph Neural Networks #Complexity and Algorithms in Graphs #Subgraph isomorphism problem #Graph factorization #Computer science #Factor-critical graph #Induced subgraph isomorphism problem #Matching (statistics) #Computation #Theoretical computer science #Pruning #3-dimensional matching #Graph #Spanning tree #Vertex (graph theory) #Algorithm #Mathematics #Line graph #Bipartite graph #Combinatorics #Voltage graph
- Enhancing non-melonic triangulations: A tensor model mixing melonic and planar maps
2015/02/04 by Valentin Bonzom, Thibault Delepouve, Vincent Rivasseau · 1 citation
Mathematics · Physics and Astronomy · #Black Holes and Theoretical Physics #Combinatorics #Computer science #Cosmology and Gravitation Theories #Coupling constant #Exponent #Mathematics #Mixing (physics) #Noncommutative and Quantum Gravity Theories #Physics #Planar #Pure mathematics #Quantum mechanics #Quartic function #Rank (graph theory) #Spanning tree #Statistical physics #Tensor (intrinsic definition) #hep-th #math-ph #math.CO #math.MP #msc:81T99
- Parallelization of Minimum Spanning Tree Algorithms Using Distributed Memory Architectures
2014/01/01 by Vladimir Lončar, Srdjan Škrbić, Antun Balaž · 1 citation
Computer Science · Mathematics · #Advanced Database Systems and Queries #Algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Distributed minimum spanning tree #Mathematics #Minimum spanning tree #Parallel Computing and Optimization Techniques #Parallel computing #Spanning tree #Tree (set theory)
- Dimension of the loop-erased random walk in three dimensions
2010/08/31 by David B. Wilson · 1 citation
Mathematics · Physics and Astronomy · #Abelian sandpile model #Combinatorics #Complex Network Analysis Techniques #Condensed matter physics #Cubic crystal system #Dimension (graph theory) #Fractal #Geometry #Heterogeneous random walk in one dimension #Lattice (music) #Loop (graph theory) #Loop-erased random walk #Mathematical analysis #Mathematics #Physics #Random walk #Scaling #Spanning tree #Statistical physics #Statistics #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #cond-mat.stat-mech #msc:05C05 #msc:60C05 #msc:82B20
- 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
- An approximation algorithm for the maximum leaf spanning arborescence problem
2010/06/01 by Matthew Drescher, Adrian Vetta · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Advanced Combinatorial Mathematics #Subroutine #Spanning tree #Combinatorics #Mathematics #Approximation algorithm #Class (philosophy) #Discrete mathematics #Algorithm #Computer science #Artificial intelligence
- Sandpile groups and spanning trees of directed line graphs
2009/06/30 by Lionel Levine · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Abelian group #Abelian sandpile model #Combinatorics #Corollary #Discrete mathematics #Geometric and Algebraic Topology #Mathematics #Physics #Spanning tree #Theoretical and Computational Physics #Topological and Geometric Data Analysis #math.CO #msc:05C05 #msc:05C20 #msc:05C25 #msc:05C50
- 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
- Truchet curves and surfaces
2007/11/10 by Cameron Browne · 1 citation
Arts and Humanities · Computer Science · Mathematics · #Cartography #Combinatorics #Computational Geometry and Mesh Generation #Contour line #Cultural Heritage Materials Analysis #Curvature #Geography #Geometry #Graph #Mathematics #Minimum spanning tree #Perimeter #Spanning tree #Surface (topology) #Topological and Geometric Data Analysis #Tree (set theory)
- A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs)
2005/06/24 by David A. Bader, Guojing Cong · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Caching and Content Delivery #Complexity and Algorithms in Graphs #Computer science #Locality #Mathematics #Minimum spanning tree #Network topology #Parallel algorithm #Parallel computing #Spanning tree #Speedup #Tree (set theory)
- A tool for filtering information in complex systems
2005/01/31 by Michele Tumminello, M. Tumminello, T. Aste +5 · 57 citations
Economics, Econometrics and Finance · Mathematics · Physics and Astronomy · #Algorithm #Biology #Combinatorics #Complex Network Analysis Techniques #Complex Systems and Time Series Analysis #Computer science #Filter (signal processing) #Genus #Graph #Mathematics #Opinion Dynamics and Social Influence #Planar #Spanning tree #Theoretical computer science #cond-mat.dis-nn #cond-mat.stat-mech #physics.soc-ph
- Conformal invariance of planar loop-erased random walks and uniform spanning trees
2004/01/01 by Gregory F. Lawler, Oded Schramm, Wendelin Werner · 2 citations
Mathematics · Physics and Astronomy · #Stochastic processes and statistical mechanics #Mathematical Dynamics and Fractals #Theoretical and Computational Physics #Mathematics #Scaling limit #Loop-erased random walk #Spanning tree #Simply connected space #Invariant (physics) #Combinatorics #Scaling #Random tree #Limit (mathematics) #Conformal map #Planar graph #Random walk #Invariance principle #Mathematical analysis #Discrete mathematics #Random graph #Graph #Geometry #Mathematical physics
- 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)
- Long-range properties of spanning trees
2000/03/01 by Richard Kenyon · 2 citations
Mathematics · Physics and Astronomy · #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #Markov Chains and Monte Carlo Methods #Spanning tree #Tree (set theory) #Mathematics #Boundary (topology) #Bounded function #Range (aeronautics) #Minimum spanning tree #Point (geometry) #Combinatorics #Distribution (mathematics) #Scale (ratio) #Geometry #Mathematical analysis #Physics
- Generating random spanning trees more quickly than the cover time
1996/01/01 by David B. Wilson · 6 citations
Mathematics · Computer Science · Engineering · #Stochastic processes and statistical mechanics #Markov Chains and Monte Carlo Methods #Advanced Graph Theory Research #Citation #Cover (algebra) #Computer science #Spanning tree #Random access #Library science #Operations research #World Wide Web #Mathematics #Engineering #Operating system #Combinatorics
- A randomized linear-time algorithm to find minimum spanning trees
1995/03/01 by David R. Karger, Philip N. Klein, Robert E. Tarjan · 25 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
- Forests, frames, and games: Algorithms for matroid sums and applications
1992/06/01 by Harold N. Gabow, Herbert Westermann, Herbert H. Westermann · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Materials and Mechanics #Algorithm #Cardinality (data modeling) #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Discrete mathematics #Disjoint sets #Graphic matroid #Mathematics #Matroid #Matroid partitioning #Spanning tree #Structural Analysis and Optimization #Submodular set function #Theoretical computer science #Weighted matroid
- Choosing a Spanning Tree for the Integer Lattice Uniformly
1991/10/01 by Robin Pemantle · 7 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 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
- Finding All Spanning Trees of Directed and Undirected Graphs
1978/08/01 by Harold N. Gabow, Eugene W. Myers · 1 citation
Computer Science · Mathematics · #Data Management and Algorithms #Data Visualization and Analytics #Advanced Database Systems and Queries #Combinatorics #Spanning tree #Undirected graph #Mathematics #Backtracking #Connected dominating set #Directed graph #Graph #Discrete mathematics #Algorithm
- Finding Minimum Spanning Trees
1976/12/01 by David R. Cheriton, Robert E. Tarjan · 5 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
- 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
- Edge-disjoint spanning trees and depth-first search
1976/01/01 by Robert Endre Tarjan, Robert E. Tarjan · 1 citation
Computer Science · Mathematics · #Ackermann function #Advanced Combinatorial Mathematics #Algorithm #Binary logarithm #Combinatorics #Computer science #Data Management and Algorithms #Discrete mathematics #Disjoint sets #Graph #Inverse #Mathematics #Spanning tree #Theory of computation #Topological and Geometric Data Analysis #Vertex (graph theory)
- Priority queues with update and finding minimum spanning trees
1975/12/01 by D. Barton Johnson, Donald B. Johnson · 1 citation
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