首页 | 本学科首页   官方微博 | 高级检索  
     


Counting maximal independent sets in directed path graphs
Affiliation:1. Center for Advanced Computing – Algorithms and Cryptography, Department of Computing, Macquarie University, Sydney, NSW 2109, Australia;2. Center for Information Security, School of Electrical Engineering and Computer Science, Queensland University of Technology, Brisbane, QLD 4000, Australia;3. Clayton School of Information Technology, Monash University, Clayton, VIC 3800, Australia;1. Department of Pure and Applied Mathematics, University of Johannesburg, Auckland Park, 2006, South Africa;2. Department of Mathematics, Furman University, Greenville, SC, USA
Abstract:The problem of counting maximal independent sets is #P-complete for chordal graphs but solvable in polynomial time for its subclass of interval graphs. This work improves upon both of these results by showing that the problem remains #P-complete when restricted to directed path graphs but that a further restriction to rooted directed path graphs admits a polynomial time solution.
Keywords:Algorithms  Maximal independent sets  Counting problem  Directed path graphs
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号