Counting Independent Sets in Claw-Free Graphs

Konstanty Junosza-Szaniawski , Zbigniew Lonc , Michał Tuczyński

Abstract

In 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.
Author Konstanty Junosza-Szaniawski (FMIS / DAC)
Konstanty Junosza-Szaniawski,,
- Department of Algebra and Combinatorics
, Zbigniew Lonc (FMIS / DAC)
Zbigniew Lonc,,
- Department of Algebra and Combinatorics
, Michał Tuczyński (FMIS / DAC)
Michał Tuczyński,,
- Department of Algebra and Combinatorics
Pages227-237
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 EnglishAlgorithm Analysis and Problem Complexity, algorithms, Computer Communication Networks, data structures, Discrete Mathematics in Computer Science, Geometry
URL http://link.springer.com/chapter/10.1007/978-3-642-25870-1_21
Score (nominal)4
Publication indicators WoS Citations = 0
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?