Notice
This item was automatically migrated from a legacy system. It's data has not been checked and might not meet the quality criteria of the present system.
Bhore, S. K., Jana, S., Pandit, S., & Roy, S. (2019). Balanced Connected Subgraph Problem in Geometric Intersection Graphs. In Combinatorial Optimization and Applications (pp. 56–68). LNCS. https://doi.org/10.1007/978-3-030-36412-0_5
E192-01 - Forschungsbereich Algorithms and Complexity
-
Published in:
Combinatorial Optimization and Applications
-
Date (published):
2019
-
Event name:
Annual International Conference on Combinatiorial Optimization and Applications (COCOA)
-
Event date:
13-Dec-2019 - 15-Dec-2019
-
Event place:
Xiamen, China
-
Number of Pages:
13
-
Publisher:
LNCS, 11949
-
Peer reviewed:
Yes
-
Abstract:
We study the Open image in new window (shortly, Open image in new window ) problem on geometric intersection graphs such as interval, circular-arc, permutation, unit-disk, outer-string graphs, etc. Given a Open image in new window graph G=(V,E), where each vertex in V is colored with either " Open image in new window " or " Open image in new window ", the BCS problem seeks a maximum cardinality in...
We study the Open image in new window (shortly, Open image in new window ) problem on geometric intersection graphs such as interval, circular-arc, permutation, unit-disk, outer-string graphs, etc. Given a Open image in new window graph G=(V,E), where each vertex in V is colored with either " Open image in new window " or " Open image in new window ", the BCS problem seeks a maximum cardinality induced connected subgraph H of G such that H is Open image in new window , i.e., H contains an equal number of red and blue vertices. We study the computational complexity landscape of the BCS problem while considering geometric intersection graphs. On one hand, we prove that the BCS problem is NP-hard on the unit disk, outer-string, complete grid, and unit square graphs. On the other hand, we design polynomial-time algorithms for the BCS problem on interval, circular-arc and permutation graphs. In particular, we give algorithms for the Open image in new window problem on both interval and circular-arc graphs, and those algorithms are used as subroutines for solving the BCS problem on the same classes of graphs. Finally, we present a FPT algorithm for the BCS problem on general graphs.