A parameterized view on matroid optimization problems
From MaRDI portal
Publication:1035682
DOI10.1016/j.tcs.2009.07.027zbMath1180.90275OpenAlexW1972514464MaRDI QIDQ1035682
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
Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)
Related Items (34)
Deterministic Truncation of Linear Matroids ⋮ Mixing Color Coding-Related Techniques ⋮ A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter ⋮ Parameterized counting of trees, forests and matroid bases ⋮ Similarity of binary relations based on rough set theory and topology: an application for topological structures of matroids ⋮ Simultaneous feedback edge set: a parameterized perspective ⋮ Finding even subgraphs even faster ⋮ Deterministic Subgraph Detection in Broadcast CONGEST. ⋮ On kernelization and approximation for the vector connectivity problem ⋮ Parameterized complexity of conflict-free matchings and paths ⋮ \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms ⋮ Full spark frames ⋮ Unnamed Item ⋮ Polynomial Kernel for Interval Vertex Deletion ⋮ FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective ⋮ Multistage \(s-t\) path: confronting similarity with dissimilarity ⋮ Representative families: a unified tradeoff-based approach ⋮ Unnamed Item ⋮ A randomized polynomial kernel for subset feedback vertex set ⋮ Stable assignment with couples: parameterized complexity and local search ⋮ Finding temporal paths under waiting time constraints ⋮ Matrix approach to spanning matroids of rough sets and its application to attribute reduction ⋮ Finding Temporal Paths Under Waiting Time Constraints. ⋮ Unnamed Item ⋮ Representative families for matroid intersections, with applications to location, packing, and covering problems ⋮ Complexity of packing common bases in matroids ⋮ Linear representation of transversal matroids and gammoids parameterized by rank ⋮ Parameterized complexity of conflict-free set cover ⋮ Fast exact algorithms for survivable network design with uniform requirements ⋮ Parameterized complexity of geometric covering problems having conflicts ⋮ Editing to Connected F-Degree Graph ⋮ Unnamed Item ⋮ Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
Cites Work
- Finding and counting given length cycles
- Parameterized coloring problems on chordal graphs
- Matroid matching and some applications
- Matroid theory and its applications in electric network theory and in statics
- Parametrized complexity theory.
- Applications of Menger's graph theorem
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Fast construction of irreducible polynomials over finite fields
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A parameterized view on matroid optimization problems
