The balanced connected subgraph problem for geometric intersection graphs

DOI10.1016/J.TCS.2022.06.030MaRDI QIDQ2166729zbMATH OpenOpenAlexWikidataFDO

Authors Sujoy Bhore, Satyabrata Jana, Supantha Pandit, Sasanka Roy

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

balanced connected subgraphcircular-arc graphscolor-balancedinterval graphsNP-hardouter-string graphspermutation graphsunit-disk graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Balanced connected subgraph problem in geometric intersection graphs
• Complexity and inapproximability results for balanced connected subgraph problem
• Algorithms and hardness results for the maximum balanced connected subgraph problem

Cites work

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

Cited in

(4)

• Complexity and inapproximability results for balanced connected subgraph problem
• Space-efficient algorithms for reachability in directed geometric graphs
• On the hardness of the Balanced Connected Subgraph Problem for families of Regular Graphs
• Sparse outerstring graphs have logarithmic treewidth

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

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