Filling crosswords is very hard

DOI10.1016/j.tcs.2023.114275OpenAlexW3199786338MaRDI QIDQ6199399

Ararat Harutyunyan, Nikolaos Melissinos, Michael Lampis, Laurent Gourvès

Publication date: 23 February 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2023.114275

zbMATH Keywords

treewidthETHcrossword puzzle

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Multigraph realizations of degree sequences: Maximization is easy, minimization is hard
• Matching is as easy as matrix inversion
• Which problems have strongly exponential complexity?
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• The complexity of restricted spanning tree problems
• On the Complexity of Timetable and Multicommodity Flow Problems
• Maximum matching of given weight in complete and complete bipartite graphs
• Parameterized Algorithms
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Filling crosswords is very hard