Circular-Arc Containment Graphs.
| dc.contributor.author | Nirkhe, M.V. | en_US |
| dc.contributor.author | Masuda, Sumio | en_US |
| dc.contributor.author | Nakajima, K. | en_US |
| dc.contributor.department | ISR | en_US |
| dc.date.accessioned | 2007-05-23T09:41:31Z | |
| dc.date.available | 2007-05-23T09:41:31Z | |
| dc.date.issued | 1988 | en_US |
| dc.description.abstract | We introduce a new class of containment graphs called circular- arc containment graphs. A graph is called a circular-arc containment graph if there exists a family of arcs on a circle, such that each vertex corresponds to an arc and two vertices are connected by an edge if and only if one of the corresponding arcs contains the other. We characterize this class of graphs by establishing its equivalence to another relatively new class of intersection graphs, called circular permutation graphs. Given a circulararc containment graph in the form of a family of arcs on a circle, we describe efficient algorithms for finding a maximum clique and a maximum independent set of the graph. | en_US |
| dc.format.extent | 610656 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | http://hdl.handle.net/1903/4782 | |
| dc.language.iso | en_US | en_US |
| dc.relation.ispartofseries | ISR; TR 1988-53 | en_US |
| dc.title | Circular-Arc Containment Graphs. | en_US |
| dc.type | Technical Report | en_US |
Files
Original bundle
1 - 1 of 1