Approximation Algorithm for the Balanced 2-Connected Bipartition Problem

DOI10.1007/978-3-319-08783-2_38zbMath1332.68288MaRDI QIDQ2920480

Weili Wu, Di Wu, Zhao Zhang, Xiao-hui Huang

Publication date: 26 September 2014

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-08783-2_38

zbMATH Keywords

interval graph; FPTAS; pseudo-polynomial time algorithm; balanced \(m\)-connected \(k\)-partition

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

05C62: Graph representations (geometric and intersection representations, etc.)