Efficient exact algorithms through enumerating maximal independent sets and other techniques
From MaRDI portal
Publication:2464327
DOI10.1007/S00224-007-1334-2zbMath1148.68054OpenAlexW2035700242MaRDI QIDQ2464327
Venkatesh Raman, Saket Saurabh, Somnath Sikdar
Publication date: 19 December 2007
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-007-1334-2
Related Items (22)
Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG ⋮ Largest chordal and interval subgraphs faster than \(2^n\) ⋮ An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set ⋮ Parameterized edge dominating set in graphs with degree bounded by 3 ⋮ An exponential time 2-approximation algorithm for bandwidth ⋮ New parameterized algorithms for the edge dominating set problem ⋮ An Exact Method for the Minimum Feedback Arc Set Problem ⋮ Exact Algorithms for Edge Domination ⋮ Exact algorithms for edge domination ⋮ A note on the parameterized complexity of unordered maximum tree orientation ⋮ Feedback Vertex Sets in Tournaments ⋮ A refined exact algorithm for edge dominating set ⋮ Parameterized Edge Dominating Set in Cubic Graphs ⋮ Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs ⋮ Algorithms for dominating clique problems ⋮ Fixed-parameter tractability results for feedback set problems in tournaments ⋮ Polynomial-time dualization of \(r\)-exact hypergraphs with applications in geometry ⋮ Iterative Compression and Exact Algorithms ⋮ Unnamed Item ⋮ Iterative Compression for Exactly Solving NP-Hard Minimization Problems ⋮ On two techniques of combining branching and treewidth ⋮ New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
This page was built for publication: Efficient exact algorithms through enumerating maximal independent sets and other techniques
