The balanced connected subgraph problem for geometric intersection graphs

DOI10.1016/j.tcs.2022.06.030OpenAlexW2971732594WikidataQ114129094 ScholiaQ114129094MaRDI QIDQ2166729

Sujoy Bhore, Sasanka Roy, Satyabrata Jana, Supantha Pandit

Publication date: 25 August 2022

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

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

zbMATH Keywords

NP-hardinterval graphspermutation graphscircular-arc graphsunit-disk graphsbalanced connected subgraphcolor-balancedouter-string graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Space-efficient algorithms for reachability in directed geometric graphs

Cites Work

• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• Spectral partitioning works: planar graphs and finite element meshes
• Unit disk graphs
• Permutation graphs: Connected domination and Steiner trees
• Connected domination and Steiner set on weighted permutation graphs
• Intersection graphs of rays and grounded segments
• Tractabilities and intractabilities on geometric intersection graphs
• Balanced connected subgraph problem in geometric intersection graphs
• The graph motif problem parameterized by the structure of the input graph
• Clique and chromatic number of circular-perfect graphs
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• Quadratic Kernelization for Convex Recoloring of Trees
• Steiner trees, connected domination and strongly chordal graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Color-coding
• Intervalizing k-colored graphs
• Reducibility among Combinatorial Problems
• Two strikes against perfect phylogeny
• Simple Geometrical Intersection Graphs
• The balanced connected subgraph problem

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