Quell

DOI10.1016/J.TCS.2015.05.044MaRDI QIDQ500997zbMATH OpenOpenAlexFDO

Authors Pedro J. Tejada, Haitao Wang, Minghui Jiang

Publication date 8 October 2015

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

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

zbMATH Keywords

approximation algorithmstraveling salesman problemfixed-parameter tractabilityhardness of approximationcombinatorial game theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial games (91A46)

Recommendations

• scientific article; zbMATH DE number 1944412
• The complexity of flood filling games
• \textsc{Pull} and \textsc{PushPull} are PSPACE-complete
• On the complexity of Two Dots for narrow boards and few colors
• The complexity of flood-filling games on graphs

Cites work

• scientific article; zbMATH DE number 2002586 (Why is no real title available?)
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• An \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• Assembling molecules in ATOMIX is hard
• Color-coding
• Computational geometry. Algorithms and applications.
• Games, puzzles, and computation
• On the approximability of the traveling salesman problem
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• On weighted vs unweighted versions of combinatorial optimization problems
• Quell
• Randolphs Robot Game is NP-hard!
• Some optimal inapproximability results
• The design of approximation algorithms

Cited in

(1)

• Quell

This page was built for publication: Quell

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