Balanced connected subgraph problem in geometric intersection graphs

DOI10.1007/978-3-030-36412-0_5zbMath1434.68347arXiv1909.03872OpenAlexW2992341946MaRDI QIDQ2180133

Satyabrata Jana, Supantha Pandit, Sujoy Bhore, Sasanka Roy

Publication date: 13 May 2020

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

zbMATH Keywords

NP-hardnessinterval graphspermutation graphsfixed-parameter tractabilitycircular-arc graphsunit-disk graphsbalanced connected subgraphcolor-balancedouter-string graphs

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (5)

Balanced connected graph partition ⋮ The balanced connected subgraph problem for geometric intersection graphs ⋮ 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: Balanced connected subgraph problem in geometric intersection graphs