Complexity and inapproximability results for balanced connected subgraph problem

DOI10.1016/j.tcs.2021.07.010OpenAlexW3185209604MaRDI QIDQ2232593

Rodolphe Giroudeau, Timothée Martinod, Benoit Darties, Valentin Pollet, Jean-Claude Konig

Publication date: 6 October 2021

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

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

zbMATH Keywords

complexityapproximationcolor-balanced subgraph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Balanced substructures in bicolored graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• Bicolored graph partitioning, or: gerrymandering at its worst
• Clustering to minimize the maximum intercluster distance
• Balanced connected subgraph problem in geometric intersection graphs
• Algorithms and hardness results for the maximum balanced connected subgraph problem
• The balanced connected subgraph problem: complexity results in bounded-degree and bounded-diameter graphs
• Hardness of r-dominating set on Graphs of Diameter (r + 1)
• An O ( n log n ) approximation scheme for Steiner tree in planar graphs
• Maximum Motif Problem in Vertex-Colored Graphs
• Reducibility among Combinatorial Problems
• Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
• The NP-completeness column: An ongoing guide
• The balanced connected subgraph problem

This page was built for publication: Complexity and inapproximability results for balanced connected subgraph problem