scientific article; zbMATH DE number 5485537

zbMATH Open1231.68051MaRDI QIDQ3549709FDOQ3549709

Authors: Harald Räcke 

Publication date: 5 January 2009

Title of this publication is not available (Why is that?)

Mathematics Subject Classification ID

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

Cited In (59)

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

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3549709)