101. Heuristics for finding largest (k,l)-sparse subgraphs
Invited abstract in session TE-2: Network Optimization, stream Discrete Optimization.
Thursday, 16:45 - 18:15Room: C 103
Authors (first author is the speaker)
| 1. | Péter Madarasi
|
| Eötvös Loránd University | |
| 2. | Lóránt Matúz
|
| Eötvös Loránd University |
Abstract
A multigraph G=(V,E) is (k,l)-sparse if every subset X of the vertices induces at most max{k|X|-l,0} edges. Finding a largest (k,l)-sparse subgraph is a well-studied, polynomial-time solvable problem, which is widely used in rigidity applications and serves as the basis of several combinatorial algorithms. We present a new implementation and compare it with previous solutions on a wide range of random and real-world datasets. The computational study shows that our implementation is consistently faster by one order of magnitude, which we even further improve by new, sophisticated heuristics for fine-tuning the algorithm. We give an in-depth practical analysis of a variety of heuristics for the order in which the algorithm processes the edges. We also implement an algorithm for finding k arc-disjoint r-arborescences in a digraph and k edge-disjoint spanning trees in an undirected graph, which are related to the case l=k. Finally, we give an improved algorithm for the case l=2k when the sparsity condition is required only for the subsets of vertices of size at least 3, which is a necessary condition for 3-dimensional rigidity when k=3.
Keywords
- Complexity and efficiency of optimization algorithms
Status: accepted
Back to the list of papers