Algorithms and hardness results for the maximum balanced connected subgraph problem

DOI10.1007/978-3-030-36412-0_24zbMath1435.68240arXiv1910.07305OpenAlexW2987075643MaRDI QIDQ2180163

Norihide Matsubara, Taiga Sone, Akihiro Yamamoto, Yasuaki Kobayashi, Kensuke Kojima

Publication date: 13 May 2020

Full work available at URL: https://arxiv.org/abs/1910.07305

zbMATH Keywords

treetreewidthinterval graphbalanced connected subgraphexact exponential-time algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (3)

Balanced substructures in bicolored graphs ⋮ Complexity and inapproximability results for balanced connected subgraph problem ⋮ The balanced connected subgraph problem

This page was built for publication: Algorithms and hardness results for the maximum balanced connected subgraph problem