Algorithm Design Using Spectral Graph Theory

No abstract is available for this paper.

• Publication year

  2013

• Venue

  Unknown venue

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1184/r1/6714635.v1
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Iterative Solution Methods

  2015cited by this paper
• Spectral sparsification of graphs: theory and algorithms

  2013cited by this paper
• Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems

  2013cited by this paper
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time

  2013cited by this paper
• A new approach to computing maximum flows using electrical flows

  2013cited by this paper
• Nearly Maximum Flows in Nearly Linear Time

  2013cited by this paper
• An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations

  2013cited by this paper
• Parallel graph decompositions using random shifts

  2013cited by this paper
• Random Rates for 0-Extension and Low-Diameter Decompositions

  2013cited by this paper
• Ligra: a lightweight graph processing framework for shared memory

  2013cited by this paper
• Efficient preconditioning of laplacian matrices for computer graphics

  2013cited by this paper
• Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back

  2013cited by this paper
• Faster approximate multicommodity flow using quadratically coupled flows

  2012cited by this paper
• Using petal-decompositions to build a low stretch spanning tree

  2012cited by this paper
• Spectral sparsification via random spanners

  2012cited by this paper
• Multiplying matrices faster than coppersmith-winograd

  2012cited by this paper
• ON HOW TO DRAW A GRAPH

  2012cited by this paper
• Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices

  2012cited by this paper
• Parallel probabilistic tree embeddings, k-median, and buy-at-bulk network design

  2012cited by this paper
• Approximate Maximum Flow on Separable Undirected Graphs

  2012cited by this paper
• The Multiplicative Weights Update Method: a Meta-Algorithm and Applications

  2012cited by this paper
• Spectral Sparsification in the Semi-streaming Setting

  2012cited by this paper
• Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs

  2011cited by this paper
• Proximity algorithms for image models: denoising

  2011cited by this paper
• Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator

  2011cited by this paper
• The Intersection Complex as a Weight Truncation and an Application to Shimura Varieties

  2011cited by this paper
• A Nearly-m log n Time Solver for SDD Linear Systems

  2011cited by this paper
• Runtime guarantees for regression problems

  2011cited by this paper
• Numerical Linear Algebra

  2011cited by this paper
• Clusterpath: an Algorithm for Clustering using Convex Fusion Penalties

  2011cited by this paper
• Efficient parallel approximation algorithms

  2011cited by this paper
• The complexity of matrix multiplication

  2011cited by this paper
• Convex optimization

  2010cited by this paper
• Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs

  2010cited by this paper
• User-Friendly Tail Bounds for Sums of Random Matrices

  2010cited by this paper
• Approaching Optimality for Solving SDD Linear Systems

  2010cited by this paper
• The Laplacian Paradigm: Emerging Algorithms for Massive Graphs

  2010cited by this paper
• Templates for convex cone problems with applications to sparse signal recovery

  2010cited by this paper
• A work-efficient parallel breadth-first search algorithm (or how to cope with the nondeterminism of reducers)

  2010cited by this paper
• Subgraph sparsification and nearly optimal ultrasparsifiers

  2009cited by this paper
• Information Flow Analysis of Interactome Networks

  2009cited by this paper
• Faster Generation of Random Spanning Trees

  2009cited by this paper
• On Element SDD Approximability

  2009cited by this paper
• A Note on Preconditioning by Low-Stretch Spanning Trees

  2009cited by this paper
• Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing

  2009cited by this paper
• Breaking the Multicommodity Flow Barrier for O(vlog n)-Approximations to Sparsest Cut

  2009cited by this paper
• The Split Bregman Method for L1-Regularized Problems

  2009cited by this paper
• Multimedia Technologies: Concepts, Methodologies, Tools, and Applications

  2008cited by this paper
• Faster approximate lossy generalized flow via interior point algorithms

  2008cited by this paper
• Finding sparse cuts locally using evolving sets

  2008cited by this paper
• Graph sparsification by effective resistances

  2008cited by this paper
• Nearly Tight Low Stretch Spanning Trees

  2008cited by this paper
• Spectral Sparsification of Graphs

  2008cited by this paper
• Twice-ramanujan sparsifiers

  2008cited by this paper
• Real-time gradient-domain painting

  2008cited by this paper
• Approximating s – t Minimum Cuts in ~ O(n 2 ) Time

  2007cited by this paper
• Support-Graph Preconditioners for 2-Dimensional Trusses

  2007cited by this paper
• An Iteratively Reweighted Norm Algorithm for Minimization of Total Variation Functionals

  2007cited by this paper
• Gradient methods for minimizing composite objective function

  2007cited by this paper
• A linear work, O(n1/6) time, parallel algorithm for solving planar Laplacians

  2007cited by this paper
• Model selection and estimation in regression with grouped variables

  2006cited by this paper
• Image Restoration with Discrete Constrained Total Variation Part I: Fast and Exact Optimization

  2006cited by this paper
• Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems

  2006cited by this paper
• Local Graph Partitioning using PageRank Vectors

  2006cited by this paper
• Sparsity and smoothness via the fused lasso

  2005cited by this paper
• Image processing and analysis - variational, PDE, wavelet, and stochastic methods

  2005cited by this paper
• Second-order Cone Programming Methods for Total Variation-Based Image Restoration

  2005cited by this paper
• Sampling from large matrices: An approach through geometric functional analysis

  2005cited by this paper
• Solving Elliptic Finite Element Systems in Near-Linear Time with Support Preconditioners

  2004cited by this paper
• Report

  2004cited by this paper
• Lower-stretch spanning trees

  2004cited by this paper
• Are Loss Functions All the Same?

  2004cited by this paper
• Poisson image editing

  2003cited by this paper
• Iterative methods for sparse linear systems

  2003cited by this paper
• A tight bound on approximating arbitrary metrics by tree metrics

  2003cited by this paper
• Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time O(m1.31)

  2003cited by this paper
• Optimal oblivious routing in polynomial time

  2003cited by this paper
• Thesis

  2002cited by this paper
• What energy functions can be minimized via graph cuts?

  2002cited by this paper
• Introduction to algorithms [2nd ed.]

  2001cited by this paper
• A multigrid tutorial, Second Edition

  2000cited by this paper
• Strong converse for identification via quantum channels

  2000cited by this paper
• INVERSE PROBLEMS NEWSLETTER

  1999cited by this paper
• LAPACK Users' guide (third ed.)

  1999cited by this paper
• Adaptive game playing using multiplicative weights

  1999cited by this paper
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

  1999cited by this paper
• Introduction to parallel algorithms

  1998cited by this paper
• On approximating arbitrary metrices by tree metrics

  1998cited by this paper
• A Randomized Parallel Algorithm for Single-Source Shortest Paths

  1997cited by this paper
• Beyond the flow decomposition barrier

  1997cited by this paper
• Topics in Optimization and Sparse Linear Systems

  1997cited by this paper
• On Information and Sufficiency

  1997cited by this paper
• Normalized cuts and image segmentation

  1997cited by this paper
• Probabilistic approximation of metric spaces and its algorithmic applications

  1996cited by this paper
• Programming parallel algorithms

  1996cited by this paper
• Spectral partitioning works: planar graphs and finite element meshes

  1996cited by this paper
• Regression Shrinkage and Selection via the Lasso

  1996cited by this paper
• Introduction to algorithms

  1996cited by this paper
• Randomized algorithms

  1995cited by this paper
• Packing directed circuits fractionally

  1995cited by this paper

• Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure

  2025cites this paper
• Spectral reordering for faster elasticity simulations

  2024cites this paper
• The Laplacian Paradigm in Deterministic Congested Clique

  2023cites this paper
• The Laplacian Paradigm in the Broadcast Congested Clique

  2022cites this paper
• Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers

  2020cites this paper
• Approximate Inverse Chain Preconditioner: Iteration Count Case Study for Spectral Support Solvers

  2020cites this paper
• Augmenting the Algebraic Connectivity of Graphs

  2020cites this paper
• SF-GRASS: Solver-Free Graph Spectral Sparsification

  2020cites this paper
• Minor Sparsifiers and the Distributed Laplacian Paradigm

  2020cites this paper
• GRASS: Graph Spectral Sparsification Leveraging Scalable Spectral Perturbation Analysis

  2019cites this paper
• D S ] 1 2 Fe b 20 15 Spectral Sparsification of Random-Walk Matrix Polynomials

  2018cites this paper
• Similarity-Aware Spectral Sparsification by Edge Filtering

  2017cites this paper
• Shortest paths, Markov chains, matrix scaling and beyond : improved algorithms through the lens of continuous optimization

  2017cites this paper
• A Hardware/Software Codesign for the Chemical Reactivity of BRAMS

  2017cites this paper
• Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More

  2016cites this paper
• A Framework for Analyzing Resparsification Algorithms

  2016cites this paper
• Simple Parallel and Distributed Algorithms for Spectral Graph Sparsification

  2016influential citation
• Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification

  2015influential citation
• Faster Spectral Sparsification of Laplacian and SDDM Matrix Polynomials

  2015cites this paper
• 2015 Faster Spectral Sparsification of Laplacian and SDDM Matrix Polynomials

  2015cites this paper
• Spectral Sparsification of Random-Walk Matrix Polynomials

  2015influential citation
• An Efficient Parallel Algorithm for Spectral Sparsification of Laplacian and SDDM Matrix Polynomials

  2015cites this paper
• Simple parallel and distributed algorithms for spectral graph sparsification

  2014influential citation
• Scalable Parallel Factorizations of SDD Matrices and Efficient Sampling for Gaussian Graphical Models

  2014influential citation
• A Note on Cut-Approximators and Approximating Undirected Max Flows

  2014cites this paper
• Preconditioning in Expectation

  2014influential citation
• Approximate Undirected Maximum Flows in O(mpolylog(n)) Time

  2014cites this paper
• Solving SDD linear systems in nearly mlog1/2n time

  2014cites this paper
• Solving 1-Laplacians in Nearly Linear Time: Collapsing and Expanding a Topological Ball

  2014cites this paper