Please use this identifier to cite or link to this item: http://hdl.handle.net/10263/7186
Full metadata record
DC FieldValueLanguage
dc.contributor.authorJana, Satyabrata-
dc.date.accessioned2021-08-06T09:19:46Z-
dc.date.available2021-08-06T09:19:46Z-
dc.date.issued2021-07-
dc.identifier.citation198p.en_US
dc.identifier.urihttp://hdl.handle.net/10263/7186-
dc.descriptionThesis under the supervision of Dr. Sasanka Royen_US
dc.description.abstractFor a set of geometric objects, the associative geometric intersection graph is the graph with a vertex for each object and an edge between two vertices if and only if the corresponding objects intersect. Geometric intersection graphs are very important due to their theoretical properties and applicability. Based on the different geometric objects, several types of geometric intersection graphs are defined. Given a graph G, an induced (either vertex or edge) subgraph H µG is said to be an well-structured subgraph if H satisfies certain properties among the vertices in H. This thesis studies some well-structured subgraphs finding problems on various geometric intersection graphs. We mainly focus on computational aspects of the problems. In each problem, either we obtain polynomial-time exact algorithm or show NP-hardness. In some cases, we also extend our study to design efficient approximation algorithms and fixed-parameter tractable algorithms. We study the construction of the planar Manhattan network (between every pair of nodes there is a minimum-length rectilinear path) of linear size for a given convex point set. We consider the maximum bipartite subgraph problem, where given a set S of n geometric objects in the plane, we want to compute a maximum-size subset S0 µ S such that the intersection graph of the objects in S0 is bipartite. We consider a variation of stabbing (hitting), dominating, and independent set problems on intersection graphs of bounded faces of a planar subdivision induced by a set of axis-parallel line segments in the plane. We investigate the problem of finding a maximum cardinality uniquely restricted matching (having no other matching that matches the same set of vertices) in proper interval graphs and bipartite permutation graphs. Finally, we consider the balanced connected subgraph problem on red-blue graphs (the color of each vertex is either red or blue). Here the goal is to find a maximum-sized induced connected subgraph that contains the same number of red and blue vertices.en_US
dc.language.isoenen_US
dc.publisherIndian Statistical Institute,Kolkataen_US
dc.relation.ispartofseriesISI Ph. D Thesis;TH510-
dc.subjectGeometric Intersection Graphsen_US
dc.subjectMaximum Bipartite Subgraphen_US
dc.subjectNP-hardness-
dc.titleComputing Well-Structured Subgraphs in Geometric Intersection Graphsen_US
dc.typeThesisen_US
Appears in Collections:Theses

Files in This Item:
File Description SizeFormat 
Thesis_Satyabrata_Jana.pdf3.3 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.