Finding good approximate vertex and edge partitions is NP-hard
From MaRDI portal
Publication:1198051
DOI10.1016/0020-0190(92)90140-QzbMath0764.68061MaRDI QIDQ1198051
Publication date: 16 January 1993
Published in: Information Processing Letters (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)
Related Items (53)
Extended cuts ⋮ Parameterized graph separation problems ⋮ Finding the biased-shortest path with minimal congestion in networks via linear-prediction of queue length ⋮ Network bipartitioning in the anti-communicability Euclidean space ⋮ A review on spectral clustering and stochastic block models ⋮ Continuous quadratic programming formulations of optimization problems on graphs ⋮ A quality and distance guided hybrid algorithm for the vertex separator problem ⋮ Improvements on Spectral Bisection ⋮ Using domain decomposition to find graph bisectors ⋮ Moving clusters within a memetic algorithm for graph partitioning ⋮ A branch-and-price algorithm for capacitated hypergraph vertex separation ⋮ An experimental evaluation of local search heuristics for graph partitioning ⋮ General variable neighborhood search for computing graph separators ⋮ ILP-Based Local Search for Graph Partitioning ⋮ The vertex \(k\)-cut problem ⋮ Spectral bisection with two eigenvectors ⋮ Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem ⋮ Scalable timing-aware network design via Lagrangian decomposition ⋮ Fission: Practical algorithms for computing minimum balanced node separators ⋮ On integer and bilevel formulations for the \(k\)-vertex cut problem ⋮ An exact algorithm for solving the vertex separator problem ⋮ Balanced graph partitioning based on mixed 0-1 linear programming and iteration vertex relocation algorithm ⋮ Parallel multilevel algorithms for hypergraph partitioning ⋮ On treewidth, separators and Yao's garbling ⋮ Structure Detection in Mixed-Integer Programs ⋮ A note on edge-based graph partitioning and its linear algebraic structure ⋮ The Effect of Various Sparsity Structures on Parallelism and Algorithms to Reveal Those Structures ⋮ Knowledge Discovery in Graphs Through Vertex Separation ⋮ A multilevel bilinear programming algorithm for the vertex separator problem ⋮ The critical node detection problem in networks: a survey ⋮ A hybrid breakout local search and reinforcement learning approach to the vertex separator problem ⋮ Partitioning (hierarchically clustered) complex networks via size-constrained graph clustering ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ IMPROVED EFFICIENT ROUTING STRATEGY ON SCALE-FREE NETWORKS ⋮ Computing semantic clusters by semantic mirroring and spectral graph partitioning ⋮ The restrictive \(H\)-coloring problem ⋮ Solution methods for the vertex variant of the network system vulnerability analysis problem ⋮ A mesh partitioning algorithm for preserving spatial locality in arbitrary geometries ⋮ Balanced line separators of unit disk graphs ⋮ Transport optimization on complex networks ⋮ Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm ⋮ On the complexity of finding balanced oneway cuts ⋮ Approximating small balanced vertex separators in almost linear time ⋮ On cutting a few vertices from a graph ⋮ A Tetrahedral Space-Filling Curve for Nonconforming Adaptive Meshes ⋮ Advanced Coarsening Schemes for Graph Partitioning ⋮ Balanced cut approximation in random geometric graphs ⋮ Unnamed Item ⋮ Parallel adaptive subspace correction schemes with applications to elasticity ⋮ Parallel subgradient algorithm with block dual decomposition for large-scale optimization ⋮ On chromatic number and minimum cut ⋮ Separator-based graph embedding into multidimensional grids with small edge-congestion ⋮ A New Lower Bound on the Size of the Smallest Vertex Separator of a Graph
Cites Work
This page was built for publication: Finding good approximate vertex and edge partitions is NP-hard
