Linear-Time FPT Algorithms via Network Flow

DOI10.1137/1.9781611973402.127zbMath1423.68572arXiv1307.4927OpenAlexW2952587811MaRDI QIDQ5384089

Keigo Oka, Yoichi Iwata, Yuichi Yoshida

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1307.4927

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Linear programming (90C05)

Related Items (15)

Linear Time Parameterized Algorithms for Subset Feedback Vertex Set ⋮ Finding near-optimal independent sets at scale ⋮ Estimating the Size of Branch-and-Bound Trees ⋮ Odd cycle transversal in mixed graphs ⋮ Hitting Selected (Odd) Cycles ⋮ Data Reduction for Maximum Matching on Real-World Graphs ⋮ An Updated Experimental Evaluation of Graph Bipartization Methods ⋮ Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ Unnamed Item ⋮ A Linear-Time Parameterized Algorithm for Node Unique Label Cover ⋮ Fixed-parameter tractability for subset feedback set problems with parity constraints ⋮ On group feedback vertex set parameterized by the size of the cutset

This page was built for publication: Linear-Time FPT Algorithms via Network Flow