Erratum to: ``Multitasking capacity: hardness results and improved constructions

DOI10.1137/23M1603856MaRDI QIDQ6572999zbMATH OpenFDO

Authors Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner

Publication date 16 July 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/23M1603856

zbMATH Keywords

connected matchinghardness of approximationmultitasking

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Multitasking capacity: hardness results and improved constructions
• scientific article; zbMATH DE number 5799830
• On maximum induced matchings in bipartite graphs
• Erratum to: ``Greedy matching: guarantees and limitations
• New results on maximum induced matchings in bipartite graphs and beyond

Cites work

• Multitasking capacity: hardness results and improved constructions
• Some optimal inapproximability results
• The probabilistic method

Cited in

(1)

• Acyclic, star and injective colouring: a complexity picture for H-free graphs

This page was built for publication: Erratum to: ``Multitasking capacity: hardness results and improved constructions

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