K-balanced biclique partition: kernelization and efficient algorithms

DOI10.1016/J.TCS.2025.115410MaRDI QIDQ6930258zbMATH OpenFDO

Authors Yifei Li, Donghua Yang, Jianzhong Li

Publication date 16 September 2025

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

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115410

zbMATH Keywords

convex relaxationgraph partitioningkernelizationproperty testing

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Cites work

• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Almost optimal canonical property testers for satisfiability
• Convergence of a block coordinate descent method for nondifferentiable minimization
• Covering graphs with few complete bipartite subgraphs
• Efficiency of coordinate descent methods on huge-scale optimization problems
• scientific article; zbMATH DE number 3582190 (Why is no real title available?)
• Minimal NFA Problems are Hard
• Mod/Resc parsimony inference: theory and application
• Nearly tight approximability results for minimum biclique cover and partition
• On the complexity of nonnegative matrix factorization
• Parameter convergence for EM and MM algorithms
• Property testing and its connection to learning and approximation
• Testing k-colorability

This page was built for publication: K-balanced biclique partition: kernelization and efficient algorithms

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