A multivariate approach for weighted FPT algorithms

DOI10.1007/978-3-662-48350-3_80MaRDI QIDQ3452855zbMATH OpenOpenAlexFDO

Authors Meirav Zehavi, Hadas Shachnai

Publication date 19 November 2015

Published in Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-48350-3_80

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A multivariate framework for weighted FPT algorithms
• On efficient fixed-parameter algorithms for weighted vertex cover
• scientific article; zbMATH DE number 2080245
• Exact algorithms and applications for tree-like Weighted Set Cover
• Parameterized algorithms for d-hitting set: the weighted case

Cites work

• A multivariate framework for weighted FPT algorithms
• Algorithm engineering for color-coding with applications to signaling pathway detection
• Algorithms for k-internal out-branching
• Approximating the maximum internal spanning tree problem
• Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
• Branching and Treewidth Based Exact Algorithms
• Color-coding
• Crown reductions for the minimum weighted vertex cover problem
• Deterministic parameterized connected vertex cover
• Enumerate and measure: improving parameter budget management
• Fundamentals of parameterized complexity
• Improved algorithms for feedback vertex set problems
• Improved upper bounds for vertex cover
• Minimum bisection is fixed parameter tractable
• Mixing Color Coding-Related Techniques
• New parameterized algorithms for the edge dominating set problem
• On efficient fixed-parameter algorithms for weighted vertex cover
• On two techniques of combining branching and treewidth
• Parameterized algorithms for d-hitting set: the weighted case
• Parameterized edge dominating set in graphs with degree bounded by 3
• Representative families: a unified tradeoff-based approach
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Vertex cover: Further observations and further improvements

Cited in

(6)

• A multivariate framework for weighted FPT algorithms
• Fast algorithms for weighted myriad computation by fixed-point search
• On efficient fixed-parameter algorithms for weighted vertex cover
• scientific article; zbMATH DE number 2080245 (Why is no real title available?)
• Maximum minimal vertex cover parameterized by vertex cover
• Exact algorithms and applications for tree-like Weighted Set Cover

Describes a project that uses

Uses Software

• QNet

This page was built for publication: A multivariate approach for weighted FPT algorithms

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