A parameterized view on matroid optimization problems

DOI10.1016/J.TCS.2009.07.027zbMATH Open1180.90275OpenAlexW1972514464MaRDI QIDQ1035682FDOQ1035682

Dániel Marx

Publication date: 4 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.07.027

zbMATH Keywords

fixed-parameter tractabilitymatroidscombinatorial optmization

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• Title not available (Why is that?)
• Parametrized complexity theory.
• Title not available (Why is that?)
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Finding and counting given length cycles
• Matroid theory and its applications in electric network theory and in statics
• Applications of Menger's graph theorem
• Parameterized coloring problems on chordal graphs
• Matroid matching and some applications
• Title not available (Why is that?)
• Fast construction of irreducible polynomials over finite fields
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (46)

• Parameterized complexity of conflict-free matchings and paths
• Similarity of binary relations based on rough set theory and topology: an application for topological structures of matroids
• Title not available (Why is that?)
• \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms
• Decomposable multi-parameter matroid optimization problems.
• Deterministic Truncation of Linear Matroids
• Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions
• A multiply constrained matroid optimization problem
• Fast exact algorithms for survivable network design with uniform requirements
• Title not available (Why is that?)
• Matrix approach to spanning matroids of rough sets and its application to attribute reduction
• Representing matroids over the reals is \(\exists \mathbb{R}\)-complete
• Parameterized counting of trees, forests and matroid bases
• Representative families for matroid intersections, with applications to location, packing, and covering problems
• Parameterized complexity of conflict-free set cover
• Algorithms for measuring perturbality in matroid optimization
• Finding Temporal Paths Under Waiting Time Constraints.
• Setup optimization problems with matroid structure
• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
• Matroid optimization problems with monotone monomials in the objective
• Stable assignment with couples: parameterized complexity and local search
• FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective
• Simultaneous feedback edge set: a parameterized perspective
• A Parameterized View on Matroid Optimization Problems
• Linear representation of transversal matroids and gammoids parameterized by rank
• Parameterized complexity of geometric covering problems having conflicts
• Finding even subgraphs even faster
• Multistage \(s-t\) path: confronting similarity with dissimilarity
• Full spark frames
• Parallel algorithms for matroid intersection and matroid parity
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Title not available (Why is that?)
• Deterministic Subgraph Detection in Broadcast CONGEST.
• Polynomial Kernel for Interval Vertex Deletion
• Proportionally Fair Matching with Multiple Groups
• Mixing Color Coding-Related Techniques
• On kernelization and approximation for the vector connectivity problem
• Editing to Connected F-Degree Graph
• Shifted matroid optimization
• Title not available (Why is that?)
• Computing paths of large rank in planar frameworks deterministically
• A randomized polynomial kernel for subset feedback vertex set
• Title not available (Why is that?)
• Finding temporal paths under waiting time constraints
• Complexity of packing common bases in matroids
• Representative families: a unified tradeoff-based approach

   Recommendations

• A Parameterized View on Matroid Optimization Problems 👍 👎
• Decomposable multi-parameter matroid optimization problems. 👍 👎
• New algorithms for linear \(k\)-matroid intersection and matroid \(k\)-parity problems 👍 👎
• Title not available (Why is that?) 👍 👎
• Representative families for matroid intersections, with applications to location, packing, and covering problems 👍 👎

This page was built for publication: A parameterized view on matroid optimization problems

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