Irredundant Set Faster Than O(2 n )

DOI10.1007/978-3-642-13073-1_26MaRDI QIDQ3563010zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(4)

• Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
• Enumeration of minimal tropical connected sets
• Irredundant intervals
• 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)