A Measure of the Connection Strengths between Graph Vertices with Applications (2009)
We present a simple iterative strategy for measuring the connection strength between a pair of vertices in a graph. The method is attractive in that it has a linear complexity and can be easily...
A Multilevel Algorithm for the Minimum 2-sum Problem (2009)
Ilya Safro, Dorit Ron, Achi Brandt
In this paper we introduce a direct motivation for solving the minimum 2-sum problem, for which we present a linear-time algorithm inspired by the Algebraic Multigrid approach which is based on...
A Fast Multigrid Algorithm for Energy Minimization Under Planar Density Constraints (2009)
Ron, Dorit, Safro, Ilya, Brandt, Achi
The two-dimensional layout optimization problem reinforced by the efficient space utilization demand has a wide spectrum of practical applications. Formulating the problem as a nonlinear minimization...
Weighted aggregation for multi-level graph partitioning (2009)
Chevalier, Cédric, Safro, Ilya
Graph partitioning is a well-known optimization problem of great interest in theoretical and applied studies. Since the 1990s, many multilevel schemes have been introduced as a practical tool to...
Randomized Heuristics for Exploiting Jacobian Scarcity (2009)
Griewank and Vogel introduced the notion of Jacobian scarcity, which generalizes the properties of sparsity and rank to capture a kind of deficiency in the degrees of freedom of the Jacobian matrix...
The minimum linear arrangement problem on proper interval graphs (2006)
We present a linear time algorithm for the minimum linear arrangement problem on proper interval graphs. The obtained ordering is a 4-approximation for general interval graphs
Graph Minimum Linear Arrangement by Multilevel Weighted Edge Contractions (2006)
Ilya Safro, Dorit Ron, Achi Brandt
The minimum linear arrangement problem is widely used and studied in many practical and theoretical applications. In this paper we present a linear-time algorithm for the problem inspired by the...
A Multilevel Algorithm for the Minimum 2-sum Problem (2006)
Ilya Safro, Dorit Ron, Achi Brandt
In this paper we introduce a direct motivation for solving the minimum 2-sum problem, for which we present a linear-time algorithm inspired by the Algebraic Multigrid approach which is based on...
Multilevel algorithms for linear ordering problems (2005)
Ilya Safro, Dorit Ron, Achi Br
Linear ordering problems are combinatorial optimization problems which deal with the minimization of different functionals in which the graph vertices are mapped onto (1, 2,..., n). These problems...