Complexity and inapproximability results for balanced connected subgraph problem

DOI10.1016/J.TCS.2021.07.010MaRDI QIDQ2232593zbMATH OpenOpenAlexFDO

Authors Timothée Martinod, Valentin Pollet, B. Darties, Rodolphe Giroudeau, Jean-Claude König

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)

Recommendations

• The balanced connected subgraph problem: complexity results in bounded-degree and bounded-diameter graphs
• Algorithms and hardness results for the maximum balanced connected subgraph problem
• On the hardness of the Balanced Connected Subgraph Problem for families of Regular Graphs
• Sparse balanced partitions and the complexity of subgraph problems
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• Approximation and parameterized algorithms for balanced connected partition problems
• The balanced connected subgraph problem for geometric intersection graphs
• Balanced connected partitions of graphs: approximation, parameterization and lower bounds

Cites work

• Title not available (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Algorithms and hardness results for the maximum balanced connected subgraph problem
• Balanced connected subgraph problem in geometric intersection graphs
• Bicolored graph partitioning, or: gerrymandering at its worst
• Clustering to minimize the maximum intercluster distance
• Hardness of \(r\)-dominating set on graphs of diameter \((r + 1)\)
• Lower bounds based on the exponential time hypothesis
• 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: complexity results in bounded-degree and bounded-diameter graphs
• Upper and lower bounds for finding connected motifs in vertex-colored graphs

Cited in

(7)

• Dual connectedness of edge-bicolored graphs and beyond
• Balanced connected subgraph problem in geometric intersection graphs
• The balanced connected subgraph problem for geometric intersection graphs
• Balanced substructures in bicolored 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
• On the hardness of the Balanced Connected Subgraph Problem for families of Regular Graphs

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

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