Half-integrality, LP-branching, and FPT Algorithms (Q2816829)

From MaRDI portal

Revision as of 12:08, 12 July 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	Half-integrality, LP-branching, and FPT Algorithms	scientific article

Statements

scholarly article

0 references

Half-integrality, LP-branching, and FPT Algorithms (English)

0 references

0 references

Magnus Wahlström

0 references

0 references

SIAM Journal on Computing

0 references

publication date

26 August 2016

0 references

zbMATH Keywords

fixed parameter tractability

0 references

\(k\)-submodularity

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1137/140962838

0 references

A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

0 references

Coverings and delta-coverings

0 references

Multimatroids I. Coverings by Independent Sets

0 references

Multimatroids. II: Orthogonality, minors and connectivity

0 references

Multimatroids. IV: Chain-group representations

0 references

Multimatroids. III: Tightness and fundamental graphs

0 references

Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra

0 references

Tight lower bounds for certain parameterized NP-hard problems

0 references

Strong computational lower bounds via parameterized complexity

0 references

Designing FPT Algorithms for Cut Problems Using Randomized Contractions

0 references

A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs

0 references

An algorithm for packing non-zero \(A\)-paths in group-labelled graphs

0 references

Packing non-zero \(A\)-paths in group-labelled graphs

0 references

Characterising tractable constraints

0 references

Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

0 references

On group feedback vertex set parameterized by the size of the cutset

0 references

On Multiway Cut Parameterized above Lower Bounds

0 references

Subset Feedback Vertex Set Is Fixed-Parameter Tractable

0 references

Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems

0 references

Bisubmodular Function Minimization

0 references

Primal-dual approximation algorithms for integral flow and multicut in trees

0 references

Multiway cuts in node weighted graphs

0 references

FPT algorithms for path-transversal and cycle-transversal problems

0 references

Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations

0 references

Towards Minimizing k-Submodular Functions

0 references

Which problems have strongly exponential complexity?

0 references

A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions

0 references

Submodular Function Minimization under Covering Constraints

0 references

Linear-Time FPT Algorithms via Network Flow

0 references

A factor 2 approximation algorithm for the generalized Steiner network problem

0 references

Constraints, consistency and closure

0 references

Min CSP on Four Elements: Moving beyond Submodularity

0 references

0 references

Non-zero disjoint cycles in highly connected group labelled graphs

0 references

On the power of unique 2-prover 1-round games

0 references

Generalized roof duality and bisubmodular functions

0 references

The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization

0 references

Representative Sets and Irrelevant Vertices

0 references

Faster Parameterized Algorithms Using Linear Programming

0 references

0 references

Vertex packings: Structural properties and algorithms

0 references

Packing non-returning A-paths

0 references

Packing non-returning \(A\)-paths algorithmically

0 references

On the structure of all minimum cuts in a network and applications

0 references

0 references

Linear Time Parameterized Algorithms via Skew-Symmetric Multicuts

0 references

A combinatorial algorithm minimizing submodular functions in strongly polynomial time.

0 references

Combinatorial optimization. Polyhedra and efficiency (3 volumes)

0 references

The Complexity of Finite-Valued CSPs

0 references

A 4 <i>k</i> <sup>2</sup> kernel for feedback vertex set

0 references

Half-integrality, LP-branching and FPT Algorithms

0 references

Packing $A$-Paths in Group-Labelled Graphs via Linear Matroid Parity

0 references

The expressive power of binary submodular functions

0 references

Identifiers

zbMATH Open document ID

0 references

10.1137/140962838

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

zbMATH DE Number

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2816829

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q2816829&oldid=36269090"