- LaserTank is NP-Complete
2019/08/31 by Per Alexandersson, Petter Restadh · 1 citation
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Artificial Intelligence in Games #Column (typography) #Combinatorics #Computability, Logic, AI Algorithms #Computational complexity theory #Computer science #Mathematics #NP-complete #Telecommunications
- TrackMania is NP-complete
2014/11/21 by Franck Dernoncourt, Dernoncourt, Franck · 1 voice
Computer Science · Mathematics · #Advanced Malware Detection Techniques #Algorithm #Arithmetic #Artificial Intelligence in Games #Combinatorics #Computer science #Discrete mathematics #Geometry #Mathematical analysis #Mathematics #NP-complete #Polynomial #Reduction (mathematics) #Software Testing and Debugging Techniques #Time complexity #cs.CC
- A Polynomial Time Algorithm for the Hamilton Circuit Problem
2013/05/26 by Xinwen Jiang, Jiang, Xinwen · 1 voice
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Completeness (order theory) #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Formal Methods in Verification #Graph #Mathematical optimization #Mathematics #NP-complete #Path (computing) #Polynomial #Simple (philosophy) #Time complexity #cs.DS
- Kurodoko is NP-Complete
2012/01/01 by Jonas K ouml lker · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Finite Group Theory Research #Computer science #NP-complete #Programming language #Algorithm #Computational complexity theory
- Selected Slither Link Variants are NP-complete
2012/01/01 by Jonas K ouml lker · 1 citation
Computer Science · Social Sciences · Psychology · Mathematics · #Artificial Intelligence in Games #Digital Games and Media #Educational Games and Gamification #Computer science #Link (geometry) #Graph #Set (abstract data type) #Planar graph #NP-complete #Combinatorics #Theoretical computer science #Algorithm #Time complexity #Mathematics #Computer network #Programming language
- Approximation Hardness for Small Occurrence Instances of NP-Hard Problems
2003/01/01 by Miroslav Chlebík, Janka Chlebı́ková, Janka Chlebíková · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Approximation algorithm #Bounded function #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Hardness of approximation #Matching (statistics) #Mathematics #NP-complete #Optimization and Search Problems #Packing problems #Statistics #Time complexity #Upper and lower bounds
- Pancyclicity and NP-completeness in planar graphs
2000/01/01 by Mingchu Li, Ming-Chu Li, Derek G Corneil +2 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Completeness (order theory) #Computational Geometry and Mesh Generation #Computer science #Discrete mathematics #Graph #Mathematics #NP-complete #Optimization and Search Problems #Planar #Planar graph #Time complexity
- Approximation algorithms for NP-complete problems on planar graphs
1994/01/02 by Brenda S. Baker · 106 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Citation #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer graphics (images) #Computer science #Discrete mathematics #Graph #Mathematics #NP-complete #Planar #Planar graph #Theoretical computer science #Time complexity #World Wide Web
- Deciding Morality of Graphs is NP-complete
1993/01/01 by Tikesh Verma, T.S. Verma, J. Pearl · 1 citation
Computer Science · Mathematics · #AI-based Problem Solving and Planning #Advanced Graph Neural Networks #Bayesian Modeling and Causal Inference #Combinatorics #Computer science #Discrete mathematics #Epistemology #Mathematics #Morality #NP-complete #Philosophy #Time complexity
- Min cut is NP-complete for edge weighted trees
1988/06/01 by Burkhard Monien, B. Monien, I.H. Sudborough +1 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Completeness (order theory) #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Feedback vertex set #Graph #Interconnection Networks and Systems #Mathematics #Maximum cut #NP-complete #Planar #Planar graph #Steiner tree problem #Time complexity #Vertex (graph theory)
- The shortest common supersequence problem over binary alphabet is NP-complete
1981/01/01 by Kari‐Jouko Räihä, Kari-Jouko Räihä, Esko Ukkonen · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Alphabet #Coding theory and cryptography #Combinatorics #Discrete mathematics #Mathematics #NP-complete #String (physics) #Time complexity #semigroups and automata theory
- Node-and edge-deletion NP-complete problems
1978/01/01 by Mihalis Yannakakis · 9 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Interconnection Networks and Systems #Combinatorics #Digraph #Mathematics #Discrete mathematics #NP-complete #Subclass #Time complexity #Induced subgraph isomorphism problem #Graph #Subgraph isomorphism problem #Edge cover #Line graph #Voltage graph
- Cyclic ordering is NP-complete
1977/10/01 by Zvi Galil, Nimrod Megiddo · 1 citation
Computer Science · Engineering · Mathematics · #Combinatorics #Computer science #Constraint Satisfaction and Optimization #Discrete mathematics #Mathematics #NP-complete #Partially ordered set #Set (abstract data type) #Time complexity #graph theory and CDMA systems #semigroups and automata theory
- On Isomorphisms and Density of NP and Other Complete Sets
1977/06/01 by L. Berman, Juris Hartmanis · 5 citations
Computer Science · Mathematics · #semigroups and automata theory #Algorithms and Data Compression #Machine Learning and Algorithms #Combinatorics #Mathematics #Alphabet #Simple (philosophy) #Time complexity #Context (archaeology) #Discrete mathematics #Regular language #NP-complete #Computer science #Theoretical computer science #Automaton
- On the Complexity of Timetable and Multicommodity Flow Problems
1976/12/01 by Shimon Even, Alon Itai, Adi Shamir · 12 citations
Decision Sciences · Engineering · Mathematics · #Scheduling and Timetabling Solutions #Vehicle Routing Optimization Methods #Scheduling and Optimization Algorithms #Mathematics #Multi-commodity flow problem #Time complexity #Function (biology) #Flow (mathematics) #Combinatorics #Binary number #Computational complexity theory #NP-complete #Discrete mathematics #Mathematical optimization #Flow network #Algorithm #Arithmetic
- Some simplified NP-complete graph problems
1976/02/01 by M. R. Garey, M.R. Garey, David S. Johnson +3 · 28 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Corollary #Discrete mathematics #Graph #Hamiltonian path #Hamiltonian path problem #Mathematics #NP-complete #Optimization and Search Problems #Time complexity
- Some simplified NP-complete problems
1974/01/01 by M. R. Garey, D. S. Johnson, Larry Stockmeyer · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Hamiltonian path #Combinatorics #Corollary #Mathematics #Hamiltonian path problem #NP-complete #Discrete mathematics #Time complexity #Computational complexity theory #Undirected graph #Upper and lower bounds #Maximum cut #Graph #Algorithm