A spectral partitioning algorithm for maximum directed cut problem

DOI10.1007/978-3-319-71150-8_26zbMath1470.68064OpenAlexW2768689801MaRDI QIDQ5915860

Dong-lei Du, Da-Chuan Xu, Dongmei Zhang, Chen-Chen Wu, Zhenning Zhang

Publication date: 26 February 2018

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-71150-8_26

zbMATH Keywords

approximation algorithmspectral graph theorymaximum directed cutspectral partitioning rounding

Mathematics Subject Classification ID

Quadratic programming (90C20) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)