Multitasking Capacity: Hardness Results and Improved Constructions
DOI10.1137/18M1224672zbMath1434.68183arXiv1809.02835MaRDI QIDQ5220467
Daniel Reichman, Alexander Yu, Thomas L. Griffiths, Pasin Manurangsi, Igor Shinkar, Tal Wagner, Noga Alon, Jonathan D. Cohen
Publication date: 26 March 2020
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1809.02835
Graph theory (including graph drawing) in computer science (68R10) 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)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Small topological complete subgraphs of ``dense graphs
- Approximating maximum independent sets by excluding subgraphs
- Connected matchings in chordal bipartite graphs
- Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture
- On Arithmetic Progressions of Cycle Lengths in Graphs
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Hadwiger Number of Graphs with Small Chordality
- Approximation Resistance from Pairwise-Independent Subgroups
- On Broadcasting in Radio Networks--Problem Analysis and Protocol Design
- On the uniform-traffic capacity of single-hop interconnections employing shared directional multichannels
- Connected matchings and Hadwiger's conjecture
- On a special case of Hadwiger's conjecture
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- Nearly complete graphs decomposable into large induced matchings and their applications
- Some optimal inapproximability results
This page was built for publication: Multitasking Capacity: Hardness Results and Improved Constructions
