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
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
