The balanced connected subgraph problem: complexity results in bounded-degree and bounded-diameter graphs

DOI10.1007/978-3-030-36412-0_36MaRDI QIDQ2180175zbMATH OpenOpenAlexFDO

Authors B. Darties, Rodolphe Giroudeau, König Jean-Claude, Valentin Pollet

Publication date 13 May 2020

Full work available at URL https://doi.org/10.1007/978-3-030-36412-0_36

zbMATH Keywords

bounded degreebounded diametercomplexity

Mathematics Subject Classification ID

Connectivity (05C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Complexity and inapproximability results for balanced connected subgraph problem
• Algorithms and hardness results for the maximum balanced connected subgraph problem
• Balanced connected subgraph problem in geometric intersection graphs

Cited in

(6)

• Balanced connected subgraph problem in geometric intersection graphs
• Algorithms and hardness results for the maximum balanced connected subgraph problem
• Complexity and inapproximability results for balanced connected subgraph problem
• On the hardness of the Balanced Connected Subgraph Problem for families of Regular Graphs
• Balanced substructures in bicolored graphs
• Balanced substructures in bicolored graphs

This page was built for publication: The balanced connected subgraph problem: complexity results in bounded-degree and bounded-diameter graphs

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