scientific article

Publication date: 5 January 2009

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Network design and communication in computer systems (68M10) Approximation algorithms (68W25)

Related Items

Interpreting the basis path set in neural networks ⋮ Approximation algorithms for the weighted \(t\)-uniform sparsest cut and some other graph partitioning problems ⋮ Serving in the Dark should be done Non-Uniformly ⋮ Metric extension operators, vertex sparsifiers and Lipschitz extendability ⋮ On minimum bisection and related partition problems in graphs with bounded tree width ⋮ Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ Terminal embeddings ⋮ Bisection of bounded treewidth graphs by convolutions ⋮ Unbalanced graph partitioning ⋮ Minimum bisection is NP-hard on unit disk graphs ⋮ Fast balanced partitioning is hard even on grids and trees ⋮ Optimal cuts and partitions in tree metrics in polynomial time ⋮ Beyond good partition shapes: an analysis of diffusive graph partitioning ⋮ Affine routing for robust network design ⋮ Thresholded covering algorithms for robust and max-min optimization ⋮ A new approximation algorithm for the unbalanced min \(s\)-\(t\) cut problem ⋮ Randomized oblivious integral routing for minimizing power cost ⋮ Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions ⋮ Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions ⋮ Unnamed Item ⋮ An approximation algorithm for the generalized \(k\)-multicut problem ⋮ Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs ⋮ Sparse Semi-Oblivious Routing: Few Random Paths Suffice ⋮ Vertex Sparsification in Trees ⋮ Minimum nonuniform graph partitioning with unrelated weights ⋮ Dynamic Balanced Graph Partitioning ⋮ On the advantage of overlapping clusters for minimizing conductance ⋮ Oblivious Routing for Sensor Network Topologies ⋮ Minimum Bisection Is Fixed-Parameter Tractable ⋮ On the parameterized complexity of computing balanced partitions in graphs ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ On the approximability of robust network design ⋮ Survey on Oblivious Routing Strategies ⋮ An \(O(n^4)\) time algorithm to compute the bisection width of solid grid graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Electric routing and concurrent flow cutting ⋮ The checkpoint problem ⋮ Unnamed Item ⋮ A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs ⋮ Unbalanced graph cuts with minimum capacity ⋮ Refined Vertex Sparsifiers of Planar Graphs ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ Unnamed Item ⋮ The complexity of tree partitioning ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ An exact combinatorial algorithm for minimum graph bisection ⋮ Approximation algorithms for connected maximum cut and related problems ⋮ The minimum degree group Steiner problem ⋮ Center-based clustering under perturbation stability ⋮ Partitioning a graph into small pieces with applications to path transversal ⋮ Restricted Cuts for Bisections in Solid Grids: A Proof via Polygons ⋮ Improved analysis of online balanced clustering ⋮ Unnamed Item ⋮ Approximation algorithms for fragmenting a graph against a stochastically-located threat ⋮ Balanced partitions of trees and applications ⋮ Near-Optimal Distributed Maximum Flow ⋮ Constructing the basis path set by eliminating the path dependency