New algorithms for a simple measure of network partitioning

DOI10.1016/J.TCS.2023.113846MaRDI QIDQ2700788zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 27 April 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2023.113846

zbMATH Keywords

approximation algorithmcombinatorial optimizationgraph algorithmmax \(k\)-uncutnetwork partitioning

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Approximation and hardness results for the max \(k\)-uncut problem
• Approximation and hardness results for the max \(k\)-uncut problem
• Approximating max k-uncut via LP-rounding plus greed, with applications to densest k-subgraph
• Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph
• An approximation algorithm for max k-uncut with capacity constraints

Cites work

• \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
• A Best Possible Heuristic for the k-Center Problem
• A Complex Semidefinite Programming Rounding Approximation Algorithm for the Balanced Max-3-Uncut Problem
• A cost function for similarity-based hierarchical clustering
• A local search approximation algorithm for \(k\)-means clustering
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• A simple min-cut algorithm
• Algorithmic aspects of homophyly of networks
• An approximation algorithm for max k-uncut with capacity constraints
• Applications of approximation algorithms to cooperative games
• Approximating max k-uncut via LP-rounding plus greed, with applications to densest k-subgraph
• Approximation Algorithms for Graph Homomorphism Problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation and hardness results for the max \(k\)-uncut problem
• Approximation of dense-n/2-subgraph and the complement of min-bisection
• Community structure in social and biological networks
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Emergence of Scaling in Random Networks
• Finding k Cuts within Twice the Optimal
• Finding happiness: an analysis of the maximum happy vertices problem
• Heuristic and Special Case Algorithms for Dispersion Problems
• scientific article; zbMATH DE number 2119718 (Why is no real title available?)
• Improved approximation algorithms for MAX k-cut and MAX BISECTION
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Improved approximation algorithms for the maximum happy vertices and edges problems
• Least squares quantization in PCM
• Maximizing happiness in graphs of bounded clique-width
• On happy colorings, cuts, and structural parameterizations
• Structural Information and Dynamical Complexity of Networks
• Tackling the maximum happy vertices problem in large networks
• The maximum happy induced subgraph problem: bounds and algorithms
• The structure of scientific collaboration networks
• Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem

Cited in

(4)

• The optimal partitioning of networks
• Partitioning networks based on generalized concepts of equivalence
• Network partition via a bound of the spectral radius
• Soft happy colourings and community structure of networks

This page was built for publication: New algorithms for a simple measure of network partitioning

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