Search results for "NP-Complete problems"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Carsten Schürmann, Jatin Shah	Representing reductions of NP-complete problems in logical frameworks: a case study.	MERLIN	2003	DBLP DOI BibTeX RDF	linear logic, NP-complete problems, logical frameworks
3	Eric Bach, Anne Condon, Elton Glaser, Celena Tanguay	DNA Models and Algorithms for NP-complete Problems. (PDF / PS)	IEEE Conference on Computational Complexity	1996	DBLP DOI BibTeX RDF	3Sat, 3-Coloring, Independent Set problem, DNA algorithms, genetic algorithms, computational complexity, search problems, DNA computing, DNA computation, NP-complete problems, search algorithms, NP-hard problems
2	Sanatan Rai, George Vairaktarakis	NP-complete Problems and Proof Methodology.	Encyclopedia of Optimization	2009	DBLP DOI BibTeX RDF	Polynomial time reduction, strong NP-completeness, ordinary NP-completeness, Computational complexity, Reducibility, NP-complete problem, NP-hard problem
2	Pablo Rabanal, Ismael Rodríguez, Fernando Rubio	Applying River Formation Dynamics to Solve NP-Complete Problems.	Nature-Inspired Algorithms for Optimisation	2009	DBLP DOI BibTeX RDF
2	Gang Fang, Jin Xu, Shemin Zhang	Performing DNA computation with RecA-mediated triple-stranded DNA structure.	Natural Computing	2009	DBLP DOI BibTeX RDF	RecA protein, Satisfiability problem (SAT), Triple-stranded DNA structure, DNA computing, NP-complete problems
2	Martin Fürer	Solving NP-Complete Problems with Quantum Search.	LATIN	2008	DBLP DOI BibTeX RDF
2	Shlomi Dolev, Hen Fitoussi	The Traveling Beams Optical Solutions for Bounded NP-Complete Problems.	FUN	2007	DBLP DOI BibTeX RDF
2	Alberto Leporati, Claudio Zandron, Claudio Ferretti, Giancarlo Mauri	Solving Numerical NP-Complete Problems with Spiking Neural P Systems.	Workshop on Membrane Computing	2007	DBLP DOI BibTeX RDF
2	Fábio Protti, Maise Dantas da Silva, Jayme Luiz Szwarcfiter	Applying Modular Decomposition to Parameterized Bicluster Editing.	IWPEC	2006	DBLP DOI BibTeX RDF	edge modification problems, bicluster graphs, NP-complete problems, fixed-parameter tractability, cluster graphs
2	Scott Aaronson	Guest Column: NP-complete problems and physical reality.	SIGACT News	2005	DBLP DOI BibTeX RDF
2	Siming Huang	Inverse Problems of Some NP-Complete Problems.	AAIM	2005	DBLP DOI BibTeX RDF	pseudo-polynomial algorithm, integer programming, Inverse problem, Knapsack problem
2	Vincenzo Cutello, Giuseppe Narzisi, Giuseppe Nicosia, Mario Pavone	Clonal Selection Algorithms: A Comparative Case Study Using Effective Mutation Potentials.	ICARIS	2005	DBLP DOI BibTeX RDF	CLONALG, opt-IA, one- counting, trap functions, 2D HP Protein Structure Prediction, pattern recognition, NP-complete problems, numerical optimization, Clonal Selection Algorithms
2	Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos	Weighted Coloring: Further Complexity and Approximability Results.	ICTCS	2005	DBLP DOI BibTeX RDF	weighted coloring, line graph of bipartite graphs, Approximation algorithm, NP-complete problems, interval graphs, partial k-tree
2	Georg Gottlob, Phokion G. Kolaitis, Thomas Schwentick	Existential second-order logic over graphs: Charting the tractability frontier.	J. ACM	2004	DBLP DOI BibTeX RDF	Existential second-order logic, graph constraints, prefix classes, graph coloring, NP-complete problems, finite model theory
2	Hans L. Bodlaender, Andreas Brandstädt, Dieter Kratsch, Michaël Rao, Jeremy Spinrad	Linear Time Algorithms for Some NP-Complete Problems on (P5, Gem)-Free Graphs.	FCT	2003	DBLP DOI BibTeX RDF
2	Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier	Graph-Modeled Data Clustering: Fixed-Parameter Algorithms for Clique Generation.	CIAC	2003	DBLP DOI BibTeX RDF	edge modification problems, data clustering, NP-complete problems, exact algorithms, fixed-parameter tractability
2	Vincenzo Cutello, Giuseppe Nicosia	An Immunological Approach to Combinatorial Optimization Problems.	IBERAMIA	2002	DBLP DOI BibTeX RDF	Evolutionary Computation, Combinatorial Optimization, NP-complete problems, Immune Algorithms
2	Iyad A. Kanj, Ljubomir Perkovic	Improved Parameterized Algorithms for Planar Dominating Set.	MFCS	2002	DBLP DOI BibTeX RDF	planar dominating set, NP-complete problems, parameterized algorithms
2	Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro	On universally easy classes for NP-complete problems.	SODA	2001	DBLP DOI BibTeX RDF
2	Nicolas Courtois	Efficient Zero-Knowledge Authentication Based on a Linear Algebra Problem MinRank.	ASIACRYPT	2001	DBLP DOI BibTeX RDF	MinRank problem, rank-distance codes, syndrome decoding (SD), identification, NP-complete problems, group signatures, Zero-knowledge, ring signatures, multivariate cryptography, entity authentication
2	Bao-Liang Lu, Michinori Ichikawa	Emergence of Learning: An Approach to Coping with NP-Complete Problems in Learning.	IJCNN	2000	DBLP DOI BibTeX RDF
2	Kai Song Goh, Andrew Lim	Combining various algorithms to solve the ship berthing problem.	ICTAI	2000	DBLP DOI BibTeX RDF	ship berthing problem, acyclic list, randomized local search, genetic algorithm, performance, computational complexity, Tabu search, directed graphs, directed acyclic graph, search problems, NP-complete problems
2	Jens Gramm, Rolf Niedermeier	Faster Exact Solutions for MAX2SAT.	CIAC	2000	DBLP DOI BibTeX RDF	MAX2SAT, Maximum Cut, NP-complete problems, exact algorithms, parameterized complexity
2	Dilip Krishnaswamy, Michael S. Hsiao, Vikram Saxena, Elizabeth M. Rudnick, Janak H. Patel, Prithviraj Banerjee	Parallel Genetic Algorithms for Simulation-Based Sequential Circuit Test Generation.	VLSI Design	1997	DBLP DOI BibTeX RDF	simulation-based test generation, distributed memory MIMD machines, shared memory MIMD machines, parallel search strategies, logic testing, fault coverage, NP-complete problems, VLSI circuits, parallel genetic algorithms, sequential circuit test generation
2	Etienne Grandjean, Frédéric Olive	Monadic Logical Definability of NP-Complete Problems.	CSL	1994	DBLP DOI BibTeX RDF	Computational complexity, NP-complete problem, nondeterminism, finite model theory, monadic second-order logic, linear time, random access machine
2	R. Z. Hwang, Richard C. T. Lee	The Application of the Searching over Separators Strategy to Solve Some NP-Complete Problems on Planar Graphs.	ISAAC	1992	DBLP DOI BibTeX RDF
2	Etienne Grandjean	Linear Time Algorithms and NP-Complete Problems.	CSL	1992	DBLP DOI BibTeX RDF
2	Vassilis Zissimopoulos, Vangelis Th. Paschos, Ferhan Pekergin	On the Approximation of NP-Complete Problems by Using the Boltzmann Machine Method: The Cases of Some Covering and Packing Problems.	IEEE Trans. Computers	1991	DBLP DOI BibTeX RDF	Boltzmann machine method, minimum vertex cover, computational complexity, parallel architectures, approximation, neural nets, NP-complete problems, heuristic programming, covering, clique, combinatorial mathematics, optimal solutions, maximum independent set, set partitioning, packing problems, minimum set cover
2	Jürgen Perl	On Chaotic Behaviour of Some NP-Complete Problems.	WG	1987	DBLP DOI BibTeX RDF
2	Benjamin W. Wah, Y. W. Eva Ma	The architecture of MANIP: a parallel computer system for solving NP-complete problems.	AFIPS National Computer Conference	1981	DBLP DOI BibTeX RDF
1	Leonid Barenboim	On the Locality of Some NP-Complete Problems	CoRR	2012	DBLP BibTeX RDF
1	Otman Abdoun, Chakir Tajani, Jaafar Abouchabaka	Hybridizing PSM and RSM Operator for Solving NP-Complete Problems: Application to Travelling Salesman Problem	CoRR	2012	DBLP BibTeX RDF
1	Jorge A. Ruiz-Vanoye, Joaquín Pérez Ortega, Rodolfo A. Pazos, Ocotlán Díaz-Parra, Juan Frausto Solís, Héctor Joaquin Fraire Huacuja, Laura Cruz Reyes, José A. Martínez Flores	Survey of polynomial transformations between NP-complete problems.	J. Computational Applied Mathematics	2011	DBLP DOI BibTeX RDF
1	Alexander Y. Davydov	A Probabilistic Attack on NP-complete Problems	CoRR	2011	DBLP BibTeX RDF
1	Eduardo Hwang	Dimensionality Decrease Heuristics for NP Complete Problems	CoRR	2011	DBLP BibTeX RDF
1	Mihai Calin Feier, Camelia Lemnaru, Rodica Potolea	Solving NP-Complete Problems on the CUDA Architecture Using Genetic Algorithms.	ISPDC	2011	DBLP DOI BibTeX RDF
1	Phillip A. Laplante	Ender Wiggin Played Mafia Wars Too.	IT Professional	2011	DBLP DOI BibTeX RDF	surreptitious problem solving, social networks, information technology, NP-complete problems, NP-hard problems, crowdsourcing, Gameplay
1	Shlomi Dolev, Hen Fitoussi	Masking traveling beams: Optical solutions for NP-complete problems, trading space for time.	Theor. Comput. Sci.	2010	DBLP DOI BibTeX RDF
1	Noam Livne	All Natural NP-Complete Problems Have Average-Case Complete Versions.	Computational Complexity	2010	DBLP DOI BibTeX RDF
1	Deepak Ponvel Chermakani	Repeating Patterns in Linear Programs that express NP-Complete Problems	CoRR	2010	DBLP BibTeX RDF
1	H. T. Ng, Franco Nori	Linear-time approach for quantum factoring, searching and NP-complete problems	CoRR	2010	DBLP BibTeX RDF
1	Per Kristian Lehre, Carsten Witt	Black-box search by unbiased variation.	GECCO	2010	DBLP DOI BibTeX RDF	black-box complexity, runtime analysis
1	Kaoru Katayama, Tatsuro Okawara, Yuka Ito	A greedy algorithm for constructing a low-width generalized hypertree decomposition.	ICDT	2010	DBLP DOI BibTeX RDF
1	Holger Dell, Dieter van Melkebeek	Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses.	STOC	2010	DBLP DOI BibTeX RDF	arithmetic progression free sets, hereditary graph properties, vertex deletion problems, satisfiability, kernelization, vertex cover, parameterized complexity, probabilistically checkable proofs, feedback vertex set, sparsification
1	Daniel Lokshtanov, Jesper Nederlof	Saving space by algebraization.	STOC	2010	DBLP DOI BibTeX RDF	moebius, dynamic programming, space efficient, fourier
1	Ramamohan Paturi, Pavel Pudlák	On the complexity of circuit satisfiability.	STOC	2010	DBLP DOI BibTeX RDF	NP-completeness, circuit satisfiability
1	Boris Altshuler, Hari Krovi, Jérémie Roland	Adiabatic quantum optimization fails for random instances of NP-complete problems	CoRR	2009	DBLP BibTeX RDF
1	Emilio del Rosal García, José Miguel Rojas Siles, Rafael Núñez Hervás, Carlos Castañeda Marroquín, Alfonso Ortega de la Puente	On the Solutions of NP-Complete Problems by Means of jNEP Run on Computers.	ICAART	2009	DBLP BibTeX RDF
1	Tseren-Onolt Ishdorj, Alberto Leporati, Linqiang Pan, Jun Wang	Solving NP-Complete Problems by Spiking Neural P Systems with Budding Rules.	Workshop on Membrane Computing	2009	DBLP DOI BibTeX RDF
1	Fábio Protti, Maise Dantas da Silva, Jayme Luiz Szwarcfiter	Applying Modular Decomposition to Parameterized Cluster Editing Problems.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Edge modification problems, Bicluster graphs, NP-complete problems, Fixed-parameter tractability, Cluster graphs
1	Francesc Comellas, Jesus Martinez-Navarro	Bumblebees: a multiagent combinatorial optimization algorithm inspired by social insect behaviour.	GEC Summit	2009	DBLP DOI BibTeX RDF	adaptative complex systems, combinatorial optimization, multiagent system, graph coloring
1	Deam James Azevedo da Silva, Roberto Célio Limão de Oliveira	A multipopulation cultural algorithm based on genetic algorithm for the MKP.	GECCO	2009	DBLP DOI BibTeX RDF	multi knapsack problem, multipopulation, genetic algorithms, combinatorial optimization, cultural algorithms
1	Haizhu Chen, Zhongshi He	A Uniform Solution to HPP in Terms of Membrane Computing.	AICI	2009	DBLP DOI BibTeX RDF	Cellular Complexity Classes, HPP, Membrane Computing, Natural Computing
1	Stanislav Zivny, Peter G. Jeavons	The Complexity of Valued Constraint Models.	CP	2009	DBLP DOI BibTeX RDF
1	Hans L. Bodlaender, Stéphan Thomassé, Anders Yeo	Kernel Bounds for Disjoint Cycles and Disjoint Paths.	ESA	2009	DBLP DOI BibTeX RDF
1	Yuli Ye, Allan Borodin	Elimination Graphs.	ICALP	2009	DBLP DOI BibTeX RDF
1	Yi Cao, Joseph C. Culberson, Lorna Stewart	DP-Complete Problems Derived from Extremal NP-Complete Properties.	MFCS	2009	DBLP DOI BibTeX RDF	DP-complete, extremal problem, unfrozen, complexity, colorability, implicant
1	Nelson Rangel-Valdez, Jose Torres-Jimenez	Phase Transition in the Bandwidth Minimization Problem.	MICAI	2009	DBLP DOI BibTeX RDF	Bandwidth Minimization Problem, Phase Transition, Connected Graphs
1	Sama Goliaei, Saeed Jalili	An Optical Wavelength-Based Solution to the 3-SAT Problem.	OSC	2009	DBLP DOI BibTeX RDF	Wavelength-Based Approach, 3-SAT Problem, NP- Complete, Optical Computing, Unconventional Computing
1	Mihai Oltean, Oana Muntean	Evolutionary Design of Graph-Based Structures for Optical Computing.	OSC	2009	DBLP DOI BibTeX RDF	evolutionary algorithms, genetic programming, NP-complete, optical computing, unconventional computing
1	Dan E. Tamir, Natan T. Shaked, Wilhelmus J. Geerts, Shlomi Dolev	Combinatorial Optimization Using Electro-Optical Vector by Matrix Multiplication Architecture.	OSC	2009	DBLP DOI BibTeX RDF	The Traveling Salesman Problem, Genetic Algorithms, Parallel Processing, Combinatorial Optimization, Heuristic Search, Hill Climbing, Optical Computing
1	Stefan Porschen, Tatjana Schmidt, Ewald Speckenmeyer	On Some Aspects of Mixed Horn Formulas.	SAT	2009	DBLP DOI BibTeX RDF	Mixed Horn formula, polynomial time reduction, NP-completeness, satisfiability, exact algorithm
1	Yuriy Brun	Solving NP-complete problems in the tile assembly model.	Theor. Comput. Sci.	2008	DBLP DOI BibTeX RDF
1	Michaël Rao	Solving some NP-complete problems using split decomposition.	Discrete Applied Mathematics	2008	DBLP DOI BibTeX RDF
1	Mihai Oltean, Oana Muntean	Solving NP-Complete Problems with Delayed Signals: An Overview of Current Research Directions.	OSC	2008	DBLP DOI BibTeX RDF
1	Jeffrey Duffany	Statistical Characterization of NP-Complete Problems.	FCS	2008	DBLP BibTeX RDF
1	Robert W. Irving	Stable matching problems with exchange restrictions.	J. Comb. Optim.	2008	DBLP DOI BibTeX RDF	Matching, NP-complete problems, Stable marriage
1	Mihai Oltean, Oana Muntean	Exact Cover with Light.	New Generation Comput.	2008	DBLP DOI BibTeX RDF	Exact Cover, NP-complete Problems, Natural Computing, Optical Computing, Unconventional Computing
1	Shiyan Hu, Zhuo Li, Charles J. Alpert	A polynomial time approximation scheme for timing constrained minimum cost layer assignment.	ICCAD	2008	DBLP DOI BibTeX RDF
1	Ping Guo, Jing Chen	Arithmetic Operation in Membrane System.	BMEI	2008	DBLP DOI BibTeX RDF	Membrane system, computing model, Arithmetic Operation
1	Michail Maniatakos, Songhua Xu, Willard L. Miranker	Constraint-Based Placement and Routing for FPGAs Using Self-Organizing Maps.	ICTAI	2008	DBLP DOI BibTeX RDF
1	Wenle Zhang, Rutao Luo	An adaptive feedback neural network approach to job-shop scheduling problem.	IJCNN	2008	DBLP DOI BibTeX RDF
1	Pablo Rabanal, Ismael Rodríguez, Fernando Rubio	Finding Minimum Spanning/Distances Trees by Using River Formation Dynamics.	ANTS Conference	2008	DBLP DOI BibTeX RDF
1	Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno	On the Complexity of Reconfiguration Problems.	ISAAC	2008	DBLP DOI BibTeX RDF
1	Randy Goebel	Folk Reducibility and AI-Complete Problems.	KI	2008	DBLP DOI BibTeX RDF
1	Michael Elberfeld, Till Tantau	Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems.	MFCS	2008	DBLP DOI BibTeX RDF	circuit classes, computational complexity, bioinformatics, haplotyping, perfect phylogenies
1	Gunes Ercal, Rafit Izhak-Ratzin, Rupak Majumdar, Adam Meyerson	Frugal Routing on Wireless Ad-Hoc Networks.	SAGT	2008	DBLP DOI BibTeX RDF
1	Hubie Chen	Inverse NP Problems.	Computational Complexity	2008	DBLP DOI BibTeX RDF	68Q17, Subject classification
1	Tseren-Onolt Ishdorj, Alberto Leporati	Uniform solutions to SAT and 3-SAT by spiking neural P systems with pre-computed resources.	Natural Computing	2008	DBLP DOI BibTeX RDF	Pre-computed resourses, SAT, Membrane computing, Spiking neural P systems, 3-SAT
1	Zne-Jung Lee, Shih-Wei Lin, Kuo-Ching Ying	A Dynamical Ant Colony Optimization with Heuristics for Scheduling Jobs on a Single Machine with a Common Due Date.	Metaheuristics for Scheduling in Industrial and Manufacturing Applications	2008	DBLP DOI BibTeX RDF	Dynamical Ant Colony Optimization, Scheduling, Heuristics, Single Machine
1	Shunichi Hayashi, Mitsuru Tada	New NP-Complete Problems Associated with Lattices.	IEICE Transactions	2007	DBLP DOI BibTeX RDF
1	Moustapha Diaby	A Reply to Hofman On: "Why LP cannot solve large instances of NP-complete problems in polynomial time"	CoRR	2007	DBLP BibTeX RDF
1	Radoslaw Hofman	Why LP Cannot Solve Large Instances of NP-complete Problems in Polynomial Time.	IMECS	2007	DBLP BibTeX RDF
1	Rubing Duan, Radu Prodan, Thomas Fahringer	Performance and cost optimization for multiple large-scale grid workflow applications.	SC	2007	DBLP DOI BibTeX RDF
1	Paul Hunter, Stephan Kreutzer	Digraph measures: Kelly decompositions, games, and orderings.	SODA	2007	DBLP DOI BibTeX RDF
1	Boxin Fu, Xiangqun Song, Zijian Guo, Peng Zhang	An optimization model for container transportation network with ACO approach.	IEEE Congress on Evolutionary Computation	2007	DBLP DOI BibTeX RDF
1	Hidemi Yamachi, Hisashi Yamamoto, Yasuhiro Tsujimura, Yasushi Kambayashi	A solution method employing a multi-objective genetic algorithm to search for pareto solutions of series-parallel system component allocation problem.	IEEE Congress on Evolutionary Computation	2007	DBLP DOI BibTeX RDF
1	Christoph Ambühl, Monaldo Mastrolilli, Ola Svensson	Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling.	FOCS	2007	DBLP DOI BibTeX RDF
1	Yuriy Brun	A Discreet, Fault-Tolerant, and Scalable Software Architectural Style for Internet-Sized Networks.	ICSE Companion	2007	DBLP DOI BibTeX RDF
1	Stefan Andrei, Gabriel Manolache, Roland H. C. Yap, Victor Felea	Approximate Satisfiability Counting.	SYNASC	2007	DBLP DOI BibTeX RDF
1	Guillaume Bagan, Arnaud Durand, Etienne Grandjean	On Acyclic Conjunctive Queries and Constant Delay Enumeration.	CSL	2007	DBLP DOI BibTeX RDF
1	Yuriy Brun	Constant-Size Tileset for Solving an NP-Complete Problem in Nondeterministic Linear Time.	DNA	2007	DBLP DOI BibTeX RDF
1	Saverio Caminiti, Emanuele G. Fusco, Rossella Petreschi	A Bijective Code for k -Trees with Linear Time Encoding and Decoding.	ESCAPE	2007	DBLP DOI BibTeX RDF
1	Rhydian Lewis	On the Combination of Constraint Programming and Stochastic Search: The Sudoku Case.	Hybrid Metaheuristics	2007	DBLP DOI BibTeX RDF
1	Daniel Díaz-Pernil, Miguel A. Gutiérrez-Naranjo, Mario J. Pérez-Jiménez, Agustin Riscos-Núñez	Solving Subset Sum in Linear Time by Using Tissue P Systems with Cell Division.	IWINAC	2007	DBLP DOI BibTeX RDF
1	Giancarlo Mauri, Mario J. Pérez-Jiménez, Claudio Zandron	On a Paun's Conjecture in Membrane Systems.	IWINAC	2007	DBLP DOI BibTeX RDF
1	Daniel Díaz-Pernil, Miguel A. Gutiérrez-Naranjo, Mario J. Pérez-Jiménez, Agustin Riscos-Núñez	A Logarithmic Bound for Solving Subset Sum with P Systems.	Workshop on Membrane Computing	2007	DBLP DOI BibTeX RDF
1	Rudolf Freund, Gheorghe Paun, Mario J. Pérez-Jiménez	Polarizationless P Systems with Active Membranes Working in the Minimally Parallel Mode.	UC	2007	DBLP DOI BibTeX RDF
1	Radoslaw Hofman	Why Linear Programming cannot solve large instances of NP-complete problems in polynomial time	CoRR	2006	DBLP BibTeX RDF
1	Sreenivas Gollapudi, Ravi Kumar, D. Sivakumar	Programmable clustering.	PODS	2006	DBLP DOI BibTeX RDF	first-order formula, clustering