Balanced partitions of trees and applications

DOI10.1007/s00453-013-9802-3zbMath1315.68201OpenAlexW2272158670MaRDI QIDQ2346962

Luca Foschini, Andreas Emil Feldmann

Publication date: 26 May 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2012/3408/

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (max. 100)

Structural and algorithmic properties of 2-community structures ⋮ New Insight into 2-Community Structures in Graphs with Applications in Social Networks ⋮ The shortest connection game ⋮ Balanced tree partition problems with virtual nodes ⋮ Dynamic Balanced Graph Partitioning ⋮ The complexity of tree partitioning ⋮ Learning directed acyclic graph SPNs in sub-quadratic time

Uses Software

• ParFE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A framework for solving VLSI graph layout problems
• Balanced graph partitioning
• The hardness of approximation: Gap location
• Parallel approximation schemes for problems on planar graphs
• Scheduling of pipelined operator graphs
• Fast Balanced Partitioning Is Hard Even on Grids and Trees
• The Design of Approximation Algorithms
• An $\mathcal{O}(n^4)$ Time Algorithm to Compute the Bisection Width of Solid Grid Graphs
• Restricted Cuts for Bisections in Solid Grids: A Proof via Polygons
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• A class of bounded approximation algorithms for graph partitioning
• Minimizing Setup and Beam-On Times in Radiation Therapy
• A scalable multi-level preconditioner for matrix-free µ-finite element analysis of human bone structures
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Applications of a Planar Separator Theorem
• One-Half Approximation Algorithms for the k-Partition Problem
• Fast Approximate Graph Partitioning Algorithms
• How Good is Recursive Bisection?
• Excluded minors, network decomposition, and multicommodity flow
• Finding minimum-quotient cuts in planar graphs
• On the completeness of a generalized matching problem
• Expander flows, geometric embeddings and graph partitioning

This page was built for publication: Balanced partitions of trees and applications