Maximum cardinality neighbourly sets in quadrilateral free graphs |
| |
Authors: | K S Neethi Sanjeev Saxena |
| |
Institution: | 1.Department of Computer Science and Engineering,Indian Institute of Technology,Kanpur,India;2.Microsoft R & D,Bangalore,India |
| |
Abstract: | Neighbourly set of a graph is a subset of edges which either share an end point or are joined by an edge of that graph. The maximum cardinality neighbourly set problem is known to be NP-complete for general graphs. Mahdian (Discret Appl Math 118:239–248, 2002) proved that it is in polynomial time for quadrilateral-free graphs and proposed an \(O(n^{11})\) algorithm for the same, here n is the number of vertices in the graph, (along with a note that by a straightforward but lengthy argument it can be proved to be solvable in \(O(n^5)\) running time). In this paper we propose an \(O(n^2)\) time algorithm for finding a maximum cardinality neighbourly set in a quadrilateral-free graph. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|