On Weighted Graph Separation Problems and Flow Augmentation
From MaRDI portal
Publication:6187079
DOI10.1137/22m153118xzbMath1530.05074arXiv2208.14841MaRDI QIDQ6187079
No author found.
Publication date: 10 January 2024
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2208.14841
parameterized complexitydirected flow augmentationweighted directed subset feedback vertex setweighted group feedback vertex setweighted multicut
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Signed and weighted graphs (05C22) Flows in graphs (05C21)
Cites Work
- Unnamed Item
- Unnamed Item
- On group feedback vertex set parameterized by the size of the cutset
- FPT algorithms for path-transversal and cycle-transversal problems
- List H-coloring a graph by removing few vertices
- Finding odd cycle transversals.
- Parameterized graph separation problems
- Constant ratio fixed-parameter approximation of the edge multicut problem
- Almost 2-SAT is fixed-parameter tractable
- Half-integrality, LP-branching, and FPT Algorithms
- Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
- On Multiway Cut Parameterized above Lower Bounds
- Finding small separators in linear time via treewidth reduction
- Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- Designing FPT Algorithms for Cut Problems Using Randomized Contractions
- The complexity of temporal constraint satisfaction problems
- Directed multicut is W[1-hard, even for four terminal pairs]
- Multicut Is FPT
- Compression via Matroids
- Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- Randomized Contractions Meet Lean Decompositions
- Representative Sets and Irrelevant Vertices
- Fixed-parameter tractability of multicut parameterized by the size of the cutset
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
- The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable
- Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
- Parameterized complexity of weighted multicut in trees
- Directed flow-augmentation
This page was built for publication: On Weighted Graph Separation Problems and Flow Augmentation
