The balanced connected subgraph problem

DOI10.1016/j.dam.2020.12.030zbMath1494.05027arXiv1809.08856OpenAlexW3122035082MaRDI QIDQ5918764

Joseph S. B. Mitchell, Sasanka Roy, Sourav Chakraborty, Satyabrata Jana, Supantha Pandit, Sujoy Bhore

Publication date: 4 August 2022

Published in: Discrete Applied Mathematics, Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

planar graphsbipartite graphstreespolynomial algorithmschordal graphssplit graphsNP-hardnessbalanced connected subgraphcolor-balanced

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (6)

Balanced connected graph partition ⋮ The balanced connected subgraph problem for geometric intersection graphs ⋮ Balanced substructures in bicolored graphs ⋮ Vertex covering with capacitated trees ⋮ Complexity and inapproximability results for balanced connected subgraph problem ⋮ The balanced connected subgraph problem

Cites Work

• Unnamed Item
• Unnamed Item
• An optimal algorithm for the Euclidean bottleneck full Steiner tree problem
• Maximum balanced subgraph problem parameterized above lower bound
• Balanced partitions of 3-colored geometric sets in the plane
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• Geometric planar networks on bichromatic points
• Finding induced trees
• Planar bichromatic minimum spanning trees
• Colorful induced subgraphs
• Induced matchings
• Bipartite embeddings of trees in the plane
• Maximum colorful cliques in vertex-colored graphs
• 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
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• The graph motif problem parameterized by the structure of the input graph
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
• PARTITIONING COLORED POINT SETS INTO MONOCHROMATIC PARTS
• The NP-completeness column: An ongoing guide
• The balanced connected subgraph problem
• The dense \(k\)-subgraph problem
• Matching colored points in the plane: Some new results

This page was built for publication: The balanced connected subgraph problem