Diverse collections in matroids and graphs

DOI10.1007/s10107-023-01959-zarXiv2101.04633OpenAlexW3120602086MaRDI QIDQ6201861

Petr A. Golovach, Saket Saurabh, Geevarghese Philip, Fahad Panolan, Fedor V. Fomin

Publication date: 21 February 2024

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

graphsmatroidsparameterized complexitydiversity of solutions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• The complexity of computing the permanent
• Bicycle dimension and special points of the Tutte polynomial
• The complexity of computing the Tutte polynomial on transversal matroids
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity of packing common bases in matroids
• Diversity of solutions: an exploration through the lens of fixed-parameter tractability theory
• On the complexity of packing rainbow spanning trees
• Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
• On Disjoint Common Bases in Two Matroids
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• The NP-Completeness of Edge-Coloring
• A weighted matroid intersection algorithm
• Kernelization
• On the Complexity of Computing the Tutte Polynomial of Bicircular Matroids
• Parameterized Algorithms
• Lehmans switching game and a theorem of Tutte and Nash-Williams
• Matroids and the greedy algorithm
• Diverse Pairs of Matchings