Counting Independent Sets in Claw-Free Graphs
Konstanty Junosza-Szaniawski , Zbigniew Lonc , Michał Tuczyński
AbstractIn this paper we give an algorithm for counting the number of all independent sets in a claw-free graph which works in time O *(1.08352 n ) for graphs with no vertices of degree larger than 3 and O *(1.23544 n ) for arbitrary claw-free graphs, where n is the number of vertices in the instance graph.
|Book||Kolman Petr, Kratochvíl Jan (eds.): Graph-Theoretic Concepts in Computer Science, Lecture Notes In Computer Science, no. 6986, 2011, Springer Berlin Heidelberg, ISBN 978-3-642-25869-5, 978-3-642-25870-1|
|Keywords in English||Algorithm Analysis and Problem Complexity, algorithms, Computer Communication Networks, data structures, Discrete Mathematics in Computer Science, Geometry|
|Publication indicators||= 0|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.