Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
From MaRDI portal
Publication:2957896
DOI10.4230/LIPIcs.STACS.2013.341zbMath1354.68135arXiv1301.1517OpenAlexW1572898177MaRDI QIDQ2957896
Publication date: 30 January 2017
Full work available at URL: https://arxiv.org/abs/1301.1517
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (16)
New Limits to Classical and Quantum Instance Compression ⋮ Rural postman parameterized by the number of components of required edges ⋮ On the complexity landscape of connected \(f\)-factor problems ⋮ On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems ⋮ Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem ⋮ Diverse collections in matroids and graphs ⋮ Aligned Drawings of Planar Graphs ⋮ Parameterized algorithms for list \(K\)-cycle ⋮ Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials ⋮ Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation) ⋮ Aligned Drawings of Planar Graphs ⋮ On some FPT problems without polynomial Turing compressions ⋮ The Steiner cycle and path cover problem on interval graphs ⋮ Shortest Two Disjoint Paths in Polynomial Time ⋮ Parameterized Pre-Coloring Extension and List Coloring Problems ⋮ Parameterized complexity of list coloring and max coloring
This page was built for publication: Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
