An algorithm for finding the Independence Number of a graph

Simple item page
dc.creatorKettani, Omar
dc.date2008-01-03
dc.date2008-01-09
dc.date.accessioned2026-07-07T08:53:11Z
dc.date.available2026-07-07T08:53:11Z
dc.descriptionIn this paper, we prove that for every connected graph G, there exists a split graph H with the same independence number and the same order. Then we propose a first algorithm for finding this graph, given the degree sequence of the input graph G. Further, we propose a second algorithm for finding the independence number of G, given the adjacency matrix of G.
dc.description15 pages; a corrected proof for the second method is added
dc.identifierhttps://arxiv.org/abs/0801.0590
dc.identifierhttp://arxiv.org/abs/0801.0590
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/145534
dc.subjectDiscrete Mathematics
dc.subjectData Structures and Algorithms
dc.subjectF.2.2
dc.titleAn algorithm for finding the Independence Number of a graph
dc.typetext

Files

Collections

arXiv