Irredundant Set Faster Than O(2 n )

DOI10.1007/978-3-642-13073-1_26zbMATH Open1284.05279OpenAlexW2033467899MaRDI QIDQ3563010FDOQ3563010

Authors: Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk 

Publication date: 28 May 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13073-1_26

Recommendations

• An Efficient Algorithm for Finding an Irredundant Set Cover
• The complexity of irredundant sets parameterized by size
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• A faster pseudopolynomial time algorithm for subset sum
• Faster exact algorithms for some terminal set problems
• Faster exact algorithms for some terminal set problems
• Faster exponential-time algorithms for approximately counting independent sets
• Solving connected dominating set faster than \(2^n\)
• Solving Connected Dominating Set Faster Than 2 n
• Combinatorial Pattern Matching

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Cited In (4)

• Enumeration of minimal tropical connected sets
• Irredundant intervals
• Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
• Moderately exponential time algorithms for the maximum induced matching problem

This page was built for publication: Irredundant Set Faster Than O(2 n )

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3563010)