Search results for "NP-completeness"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
12	Paolo Liberatore	Complexity results on DPLL and resolution.	ACM Trans. Comput. Log.	2006	DBLP DOI BibTeX RDF	Davis-Putnam, NP-completeness, propositional satisfiability
12	Duhong Chen, Oliver Eulenstein, David Fernández-Baca, Michael J. Sanderson	Minimum-Flip Supertrees: Complexity and Algorithms.	IEEE ACM Trans. Comput. Biol. Bioinform.	2006	DBLP DOI BibTeX RDF	tree assembly, NP-completeness, Phylogenetic tree, supertree
12	Jianping Wang 0001, Mei Yang, Bin Yang, S. Q. Zheng 0001	Dual-Homing Based Scalable Partia Multicast Protection.	IEEE Trans. Computers	2006	DBLP DOI BibTeX RDF	complexity, Networks, multicast, NP-completeness, survivability, protection
12	Daniele Mundici	A Characterization of the free n-generated MV-algebra.	Arch. Math. Log.	2006	DBLP DOI BibTeX RDF	Free MV-algebra, Chang completeness theorem, McNaughton theorem, standard triangulation of the n-cube, Partition of unity, ?-functor, Singular homology group, Pyramidal function, MV-algebra, piecewise linear function
12	Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg	Nash equilibria in graphical games on trees revisited.	EC	2006	DBLP DOI BibTeX RDF	PPAD-completeness, nash equilibrium, graphical games
12	Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider	Clique-width minimization is NP-hard.	STOC	2006	DBLP DOI BibTeX RDF	absolute approximation, NP-completeness, clique-width, pathwidth
12	Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou	The complexity of computing a Nash equilibrium.	STOC	2006	DBLP DOI BibTeX RDF	PPAD-completeness, complexity, game theory, Nash equilibrium
12	Christian F. J. Lange, Michel R. V. Chaudron	Effects of defects in UML models: an experimental investigation.	ICSE	2006	DBLP DOI BibTeX RDF	UML, consistency, completeness, defect detection
12	R. C. Chakinala, Abishek Kumarasubramanian, Kofi A. Laing, R. Manokaran, C. Pandu Rangan, Rajmohan Rajaraman	Playing push vs pull: models and algorithms for disseminating dynamic data in networks.	SPAA	2006	DBLP DOI BibTeX RDF	push & pull, approximation algorithms, NP-Completeness, network design, data dissemination, multicast tree
12	Gerhard Gröger, Lutz Plümer	How to Get 3-D for the Price of 2-D-Topology and Consistency of 3-D Urban GIS.	GeoInformatica	2005	DBLP DOI BibTeX RDF	2.5-D, 2.8-D, GIS, maps, consistency, topology, completeness, correctness, axioms, 3-D
12	Roberto Giacobazzi, Francesco Ranzato, Francesca Scozzari	Making abstract domains condensing.	ACM Trans. Comput. Log.	2005	DBLP DOI BibTeX RDF	logic program analysis, abstract interpretation, completeness, linear logic, condensation, Abstract domain
12	Jian-Er Chen	Parameterized Computation and Complexity: A New Approach Dealing with NP-Hardness.	J. Comput. Sci. Technol.	2005	DBLP DOI BibTeX RDF	parameterized computation, algorithm, approximation algorithm, complexity, NP-completeness, computational
12	Stefan Porschen, Bert Randerath, Ewald Speckenmeyer	Exact 3-satisfiability is decidable in time O(20.16254n).	Ann. Math. Artif. Intell.	2005	DBLP DOI BibTeX RDF	exact satisfiability, autonomous clause pattern, formula graph, NP-completeness, perfect matching
12	Zhi-Zhong Chen, Mitsuharu Kouno	A Linear-Time Algorithm for 7-Coloring 1-Plane Graphs.	Algorithmica	2005	DBLP DOI BibTeX RDF	Plane embeddings, Plane embeddings, NP-completeness, Graph algorithms, Planar graphs, Planar graphs, Vertex coloring
12	Savio S. H. Tse	Approximate Algorithms for Document Placement in Distributed Web Servers.	IEEE Trans. Parallel Distributed Syst.	2005	DBLP DOI BibTeX RDF	Distributed Web server, document placement, document replication, file allocation problem, approximate algorithm, load balancing, NP-completeness
12	Olivier Beaumont, Arnaud Legrand, Loris Marchal, Yves Robert	Pipelining Broadcasts on Heterogeneous Platforms.	IEEE Trans. Parallel Distributed Syst.	2005	DBLP DOI BibTeX RDF	Scheduling, grids, heuristics, broadcast, NP-completeness, collective communications, heterogeneous clusters
12	Peter Oehlert	Violating Assumptions with Fuzzing.	IEEE Secur. Priv.	2005	DBLP DOI BibTeX RDF	completeness testing, comprehensive negative testing, software testing, quality assurance, boundary conditions, fuzzing
12	Jan Johannsen	The Complexity of Pure Literal Elimination.	J. Autom. Reason.	2005	DBLP DOI BibTeX RDF	pure literal, computational complexity, completeness
12	Stefan Szeider	Backdoor Sets for DLL Subsolvers.	J. Autom. Reason.	2005	DBLP DOI BibTeX RDF	unit propagation, pure literal elimination, backdoor sets, W[P]-completeness, satisfiability, parameterized complexity
12	Li Zhang	Upgrading arc problem with budget constraint.	ACM Southeast Regional Conference (1)	2005	DBLP DOI BibTeX RDF	discount factor, greedy selection, NP-completeness, diameter, decision problem
12	Peter Hachenberger, Lutz Kettner	Boolean operations on 3D selective Nef complexes: optimized implementation and experiments.	Symposium on Solid and Physical Modeling	2005	DBLP DOI BibTeX RDF	boundary evaluation, exactness, nef polyhedra, unbounded polyhedra, algorithms, data structures, benchmark, robustness, experiments, completeness, CSG, non-manifold, B-rep
12	Carsten Lutz	NEXP TIME-complete description logics with concrete domains.	ACM Trans. Comput. Log.	2004	DBLP DOI BibTeX RDF	NExpTime-completeness, concrete domains, domino problem, Computational complexity, description logic, post correspondence problem
12	Vineet Bafna, Vikas Bansal 0001	The Number of Recombination Events in a Sample History: Conflict Graph and Lower Bounds.	IEEE ACM Trans. Comput. Biol. Bioinform.	2004	DBLP DOI BibTeX RDF	ancestral recombination graph, lower bounds, NP-completeness, Recombination, haplotypes, conflict graph, phylogenetic networks
12	Hasan M. Jamil, Gillian Dobbie	On Logical Foundations of Multilevel Secure Databases.	J. Intell. Inf. Syst.	2004	DBLP DOI BibTeX RDF	MLS databases, belief assertion, inheritance and overriding, security, reasoning, deductive databases, declarative language, soundness and completeness
12	Jose Maria Turull Torres	Erratum for: A Study of Homogeneity in Relational Databases [Annals of Mathematics and Artificial Intelligence 33(2) (2001) 379-414].	Ann. Math. Artif. Intell.	2004	DBLP DOI BibTeX RDF	query computability, completeness of models, query languages, database machines
12	Tapio Elomaa, Matti Kääriäinen	The Difficulty of Reduced Error Pruning of Leveled Branching Programs.	Ann. Math. Artif. Intell.	2004	DBLP DOI BibTeX RDF	reduced error pruning, approximability, NP-completeness, concept learning, branching programs
12	Vida Dujmovic, Sue Whitesides	An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization.	Algorithmica	2004	DBLP DOI BibTeX RDF	FPT, Sided crossing minimization, Layer crossing minimization, Layer drawings, Level drawings, NP-completeness, Graph drawing, Fixed parameter tractability
12	Renate A. Schmidt, Dmitry Tishkovsky, Ullrich Hustadt	Interactions between Knowledge, Action and Commitment within Agent Dynamic Logic.	Stud Logica	2004	DBLP DOI BibTeX RDF	Agent logic, knowledge, decidability, commitments, actions, dynamic logic, multi-modal logic, abilities, soundness and completeness
12	Mikhail V. Volkov 0001	Checking quasi-identities in a finite semigroup may be computationally hard.	Stud Logica	2004	DBLP DOI BibTeX RDF	quasi-identity, NP-completeness, identity, semigroup
12	Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri	On the Power Assignment Problem in Radio Networks.	Mob. Networks Appl.	2004	DBLP DOI BibTeX RDF	ad-hoc radio networks, approximability, NP-completeness, energy consumption
12	Martin Jansche	Learning Local Transductions Is Hard.	J. Log. Lang. Inf.	2004	DBLP DOI BibTeX RDF	letter-to-sound rules, rational transductions, machine learning, natural language processing, combinatorial optimization, NP completeness, formal languages, Boolean satisfiability
12	Mohammad Sohel Rahman, Mohammod Abul Kashem	Degree restricted spanning trees of graphs.	SAC	2004	DBLP DOI BibTeX RDF	algorithms, graphs, NP-completeness, spanning trees, Hamiltonian path
12	Peter Bürgisser, Felipe Cucker	Counting complexity classes for numeric computations II: algebraic and semialgebraic sets.	STOC	2004	DBLP DOI BibTeX RDF	counting complexity classes, geometric degree, semialgebraic sets, completeness, Betti numbers, Euler characteristic
12	Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar	The complexity of pure Nash equilibria.	STOC	2004	DBLP DOI BibTeX RDF	PLS-completeness, pure Nash equilibria, complexity, games, local search, congestion games, PLS
12	Oliver Kutz, Frank Wolter, Holger Sturm, Nobu-Yuki Suzuki, Michael Zakharyaschev	Logics of metric spaces.	ACM Trans. Comput. Log.	2003	DBLP DOI BibTeX RDF	expressive completeness, Decidability, spatial reasoning, metric spaces
12	Mariangiola Dezani-Ciancaglini, Furio Honsell, Fabio Alessi	A complete characterization of complete intersection-type preorders.	ACM Trans. Comput. Log.	2003	DBLP DOI BibTeX RDF	lambda models, completeness, Lambda calculus, intersection types
12	Richard Edwin Stearns	Deterministic versus nondeterministic time and lower bound problems.	J. ACM	2003	DBLP DOI BibTeX RDF	generic problems, power index, Computational complexity, NP-completeness, time complexity, SAT, nondeterminism, generic algorithms
12	Andrei A. Krokhin, Peter Jeavons 0001, Peter Jonsson	Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra.	J. ACM	2003	DBLP DOI BibTeX RDF	Allen's algebra, dichotomy theorem, representing graphs by intervals, satisfiability of temporal constraints, tractable cases, complexity, NP-completeness
12	Valentin Goranko	The Basic Algebra of Game Equivalences.	Stud Logica	2003	DBLP DOI BibTeX RDF	game operations, game algebra, game identities, completeness, modal logic, axiomatization
12	Stacy J. Prowell, Jesse H. Poore	Foundations of Sequence-Based Software Specification.	IEEE Trans. Software Eng.	2003	DBLP DOI BibTeX RDF	sequence-based specification, trace specification, consistency, completeness, correctness, requirements analysis, Software specification
12	Morten Rhiger	A foundation for embedded languages.	ACM Trans. Program. Lang. Syst.	2003	DBLP DOI BibTeX RDF	phantom types, Haskell, completeness, Standard ML, type safety, higher-order abstract syntax, Embedded languages, type soundness
12	Christian Denger, Daniel M. Berry, Erik Kamsties	Higher Quality Requirements Specifications through Natural Language Patterns.	SwSTE	2003	DBLP DOI BibTeX RDF	embedded systems, authoring, patterns, quality, metamodel, natural language, completeness, accuracy, requirements specification, ambiguity, rewriting, precision
12	Helmut Alt, Christian Knauer, Günter Rote, Sue Whitesides	The complexity of (un)folding.	SCG	2003	DBLP DOI BibTeX RDF	linkage reconfiguration, computational geometry, PSPACE-completeness
12	Gerhard Gröger, Lutz Plümer	Exploiting 2D concepts to achieve consistency in 3D GIS applications.	GIS	2003	DBLP DOI BibTeX RDF	GIS, maps, consistency, completeness, 3D, correctness, axioms
12	Wu Jigang, Thambipillai Srikanthan	A Run-time Reconfiguration Algorithm for VLSI Arrays.	VLSI Design	2003	DBLP DOI BibTeX RDF	Degradable VLSI/WSI array, fault-tolerance, reconfiguration, NP-completeness, greedy algorithm
12	Michael R. Darnel, Jorge Martinez 0001	Radical Classes of Lattice-Ordered Groups vs. Classes of Compact Spaces.	Order	2002	DBLP DOI BibTeX RDF	F-spaces, disconnected spaces, completeness of a class, laterally separated, radical class of -groups, spectral space, stranded primes, Yosida space
12	Stephen A. Cook, Jan K. Pachl, Irwin S. Pressman	The optimal location of replicas in a network using a READ-ONE-WRITE-ALL policy.	Distributed Comput.	2002	DBLP DOI BibTeX RDF	Optimization, Dynamic programming, NP-completeness, Data replication
12	Uwe Schöning	A Probabilistic Algorithm for k -SAT Based on Limited Local Search and Restart.	Algorithmica	2002	DBLP DOI BibTeX RDF	NP-completeness, Satisfiability problem
12	Chor Ping Low, Xueyan Song	On Finding Feasible Solutions for the Delay Constrained Group Multicast Routing Problem.	IEEE Trans. Computers	2002	DBLP DOI BibTeX RDF	Delay constrained group multicast routing, feasible solutions, NP-completeness, heuristic algorithm
12	Pou-yung Lee, Albert Mo Kim Cheng	HAL: A Faster Match Algorithm.	IEEE Trans. Knowl. Data Eng.	2002	DBLP DOI BibTeX RDF	combinatorial explosion problem, algorithms, knowledge-based systems, expert systems, NP-completeness, Matching, database systems, production systems
12	Regina Estkowski, Joseph S. B. Mitchell, Xinyu Xiang	Optimal decomposition of polygonal models into triangle strips.	SCG	2002	DBLP DOI BibTeX RDF	tristrips, NP-completeness, integer programming, rendering, branch and bound, triangle strips
12	Manindra Agrawal	Pseudo-Random Generators and Structure of Complete Degrees.	CCC	2002	DBLP DOI BibTeX RDF	Completeness, Reductions, Pseudo-random Generators
12	Wing-Kwan Yeung, Ceyda Oguz, T. C. Edwin Cheng	Minimizing Weighted Number of Early and Tardy Jobs with a Common Due Window Involving Location Penalty.	Ann. Oper. Res.	2001	DBLP DOI BibTeX RDF	early-tardy job, due window, dynamic programming, NP-completeness, single machine scheduling
12	H.-P. Butzmann	An Incomplete Function Space.	Appl. Categorical Struct.	2001	DBLP DOI BibTeX RDF	convergence space, convergence vector space, completeness
12	Ivan Kramosil	Boolean-like and frequentistic nonstandard semantics for first-order predicate calculus without functions.	Soft Comput.	2001	DBLP DOI BibTeX RDF	First-order predicate calculus, Standard semantics, Boolean-like semantics, Frequentistic semantics, Completeness theorems
12	Russell Greiner, Christian Darken, N. Iwan Santoso	Efficient reasoning.	ACM Comput. Surv.	2001	DBLP DOI BibTeX RDF	efficiency trade-offs, soundness/completeness/expressibility
12	Wilfred Ng	An extension of the relational data model to incorporate ordered domains.	ACM Trans. Database Syst.	2001	DBLP DOI BibTeX RDF	Axiom system, chase rules, language expressiveness, mixed ordering, nonuniform completeness, order-preserving database automorphism, ordered SQL, ordered functional dependencies, ordered relational model, partially ordered domains, partially ordered relational algebra, pointwise ordering, valuation mapping, tableaux, lexicographical ordering, ordered relations, implication problem
12	Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, Saurabh Sethia	Optimal covering tours with turn costs.	SODA	2001	DBLP BibTeX RDF	m-guillotine subdivisions, lawn mowing, milling, turn costs, approximation algorithms, NP-completeness, traveling salesman problem (TSP), manufacturing, polynomial-time approximation scheme (PTAS), covering, NC machining
12	Chin Soon Lee, Neil D. Jones, Amir M. Ben-Amram	The size-change principle for program termination.	POPL	2001	DBLP DOI BibTeX RDF	omega automaton, program analysis, termination, partial evaluation, PSPACE-completeness
12	Sergey Baranov, Vsevolod Kotlyarov	Automation of Design and Development of Embedded Software on the Basis of a Strictly Defined Software Architecture.	COMPSAC	2001	DBLP DOI BibTeX RDF	Consistency and Completeness of Requirements, Software Architecture, Formal Specifications
12	Dimitrios Koukopoulos, Yannis C. Stamatiou	A compressed-domain watermarking algorithm for mpeg audio layer 3.	MM&Sec	2001	DBLP DOI BibTeX RDF	hard instances, mpeg audio layer 3, threshold phenomena, NP-completeness, audio watermarking
12	Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons 0001	The complexity of maximal constraint languages.	STOC	2001	DBLP DOI BibTeX RDF	algebraic invariance property, constraint satisfaciton problem, relational clone, complexity, NP-completeness, tractability, constraint language
12	Alessio Lomuscio, Ron van der Meyden, Mark Ryan 0001	Knowledge in multiagent systems: initial configurations and broadcast.	ACM Trans. Comput. Log.	2000	DBLP DOI BibTeX RDF	computational complexity, completeness
12	Nir Friedman, Joseph Y. Halpern, Daphne Koller	First-order conditional logic for default reasoning revisited.	ACM Trans. Comput. Log.	2000	DBLP DOI BibTeX RDF	KLM properties, plausibility measures, completeness, first-order logic, default reasoning, conditional logic
12	Catherine S. Greenhill	The complexity of counting colourings and independent sets in sparse graphs and hypergraphs.	Comput. Complex.	2000	DBLP DOI BibTeX RDF	#P-completeness, interpolation, independent sets, Graph colourings
12	Rolf H. Möhring, Matthias Müller-Hannemann	Complexity and Modeling Aspects of Mesh Refinement into Quadrilater.	Algorithmica	2000	DBLP DOI BibTeX RDF	Bidirected flows, cal NP -completeness, Computer-aided design, Mesh generation, Mesh decomposition
12	Chor Ping Low	An Efficient Reconfiguration Algorithm for Degradable VLSI/WSI Arrays.	IEEE Trans. Computers	2000	DBLP DOI BibTeX RDF	Degradable VLSI/WSI arrays, efficient heuristic, NP-completeness, greedy algorithm
12	Piera Barcaccia, Maurizio A. Bonuccelli, Miriam Di Ianni	Complexity of Minimum Length Scheduling for Precedence Constrained Messages in Distributed Systems.	IEEE Trans. Parallel Distributed Syst.	2000	DBLP DOI BibTeX RDF	Single hop distributed systems, minimum schedule length, scheduling, approximation algorithms, NP-completeness
12	David A. Cohen, Peter Jeavons 0001, Peter Jonsson, Manolis Koubarakis	Building tractable disjunctive constraints.	J. ACM	2000	DBLP DOI BibTeX RDF	disjunctive constraints, complexity, NP-completeness, constraint satisfaction problem, relations, independence
12	Tudor Balanescu	Generalised Stream X-Machines with Output Delimited Type.	Formal Aspects Comput.	2000	DBLP DOI BibTeX RDF	Design for test conditions, Generalised stream X-machines, Output delimited type, Test completeness, Weak output distinguishable type, W-method
12	Cynthia Dwork, Moni Naor	Zaps and Their Applications.	FOCS	2000	DBLP DOI BibTeX RDF	zap, witness-indistinguishable protocol, shared random string model, verifiable pseudo-random bit generators, concurrent deniable authentication, computational complexity, cryptography, NP completeness, theorem proving, public keys, zero-knowledge proofs, verifier, concurrent zero knowledge
12	Atsushi Togashi, Xiaosong Lu, Fumiaki Kanezashi	System Requirements and Formal Specifications of Hierarchical Reactive Systems.	ICPADS	2000	DBLP DOI BibTeX RDF	Formal Specification, Reactive System, System Requirement, State Transition System, Soundness and Completeness
12	Bernhard Beckert, Reiner Hähnle, Felip Manyà	The 2-SAT Problem of Regular Signed CNF Formulas.	ISMVL	2000	DBLP DOI BibTeX RDF	signed logic, NP-completeness, SAT, Many-valued logic
12	Agostino Dovier, Eugenio G. Omodeo, Alberto Policriti	Solvable Set/Hyperset Contexts: II. A Goal-Driven Unification Algorithm for the Blended Case.	Appl. Algebra Eng. Commun. Comput.	1999	DBLP DOI BibTeX RDF	Semantic unification, Hypersets, NP-completeness, Bisimulations, Set theory
12	P. P. Chakrabarti 0001	Partial Precedence Constrained Scheduling.	IEEE Trans. Computers	1999	DBLP DOI BibTeX RDF	Scheduling, NP-completeness, precedence constraints, shortest-path algorithms
12	Barbara J. Czerny, Mats Per Erik Heimdahl	Identifying Domain Axioms Using Binary Decision Diagrams.	HASE	1999	DBLP DOI BibTeX RDF	Static Requirements Analysis, Domain Axioms, Spurious Errors, Completeness Analysis, False Positives, Consistency Analysis, Binary Decision Diagrams (BDDs)
12	Norbert Sensen	Algorithms for a Job-Scheduling Problem within a Parallel Digital Library.	ICPP	1999	DBLP DOI BibTeX RDF	Parallel digital library, data remapping, scheduling, complexity, heuristics, NP completeness, local search, greedy algorithm
12	Russell Impagliazzo, Ramamohan Paturi	Complexity of k-SAT.	CCC	1999	DBLP DOI BibTeX RDF	NP-completeness, Satisfiability, Reductions, Complexity Theory
12	Dominique Barth, Mario Valencia-Pabon	Message Scheduling on Trees under a Generalized Line-Communication Model.	ISPAN	1999	DBLP DOI BibTeX RDF	Line-Communications, Bufferless Routing, Approximation Algorithms, NP-completeness, Tree Networks, Message Scheduling
12	Ryuhei Uehara	Another Measure for the Lexicographically First Maximal Subgraph Problems and Its Threshold Value on a Random Graph.	ISPAN	1999	DBLP DOI BibTeX RDF	the lexicographically first maximal subgraph problems, threshold function of a random graph, Analysis of algorithms, P-completeness, NC algorithms
12	Nen-Fu Huang, Huey-Ing Liu	A study of isochronous channel reuse in DQDB metropolitan area networks.	IEEE/ACM Trans. Netw.	1998	DBLP DOI BibTeX RDF	destination release, isochronous, approximation algorithm, NP-completeness, bandwidth allocation, DQDB, slot reuse
12	Zheng Tang, Okihiko Ishizuka	A Learning Multiple-Valued Logic Network: Algebra, Algorithm, and Applications.	IEEE Trans. Computers	1998	DBLP DOI BibTeX RDF	learning capability, Multiple-valued logic, backpropagation algorithm, functional completeness
12	David R. Karger, Rajeev Motwani 0001, Madhu Sudan 0001	Approximate Graph Coloring by Semidefinite Programming.	J. ACM	1998	DBLP DOI BibTeX RDF	approximation algorithms, NP-completeness, randomized algorithms, graph coloring, chromatic number
12	Sanjeev Arora, Carsten Lund, Rajeev Motwani 0001, Madhu Sudan 0001, Mario Szegedy	Proof Verification and the Hardness of Approximation Problems.	J. ACM	1998	DBLP DOI BibTeX RDF	optimization, NP-completeness, randomness, proof verification
12	C.-J. Richard Shi, Janusz A. Brzozowski	Cluster-cover a theoretical framework for a class of VLSI-CAD optimization problems.	ACM Trans. Design Autom. Electr. Syst.	1998	DBLP DOI BibTeX RDF	cluster-cover, logic minimizaiton, self-checking logic design, topological routing, NP-completeness, state assignment
12	Martin C. Cooper	The Tractability of Segmentation and Scene Analysis.	Int. J. Comput. Vis.	1998	DBLP DOI BibTeX RDF	computational complexity, segmentation, NP-completeness, scene analysis
12	Venkatesan Guruswami, Daniel Lewin 0001, Madhu Sudan 0001, Luca Trevisan	A Tight Characterization of NP with 3 Query PCPs.	FOCS	1998	DBLP DOI BibTeX RDF	Probabilistically Checkable Proofs (PCP), Proof composition, Two-prover one-round proof systems, Adaptive and non-adaptive verifiers, Completeness and soundness, Complexity Theory, Query complexity
12	Subhashis Majumder, Subhas C. Nandy, Bhargab B. Bhattacharya	Partitioning VLSI Floorplans by Staircase Channels for Global Routing.	VLSI Design	1998	DBLP DOI BibTeX RDF	maxflow-mincut, algorithms, complexity, partitioning, NP-completeness, Global routing
12	Bernd Sturmfels, Markus Wiegelmann	Structural Gröbner Basis Detection.	Appl. Algebra Eng. Commun. Comput.	1997	DBLP DOI BibTeX RDF	Gröbner basis, Variation of term orders, System of polynomial equations, NP-completeness, Polynomial time algorithm
12	Stephen R. Tate	Band Ordering in Lossless Compression of Multispectral Images.	IEEE Trans. Computers	1997	DBLP DOI BibTeX RDF	Compression, NP-completeness, image compression, lossless compression, multispectral images, satellite data
12	R. Sekar 0001, I. V. Ramakrishnan, Prateek Mishra	On the power and limitations of strictness analysis.	J. ACM	1997	DBLP DOI BibTeX RDF	program analysis, abstract interpretation, completeness, strictness analysis
12	Peter Jeavons 0001, David A. Cohen, Marc Gyssens	Closure properties of constraints.	J. ACM	1997	DBLP DOI BibTeX RDF	indicator problem, complexity, NP-completeness, constraint satisfaction problem
12	Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe	Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP.	J. ACM	1997	DBLP DOI BibTeX RDF	Lewis Carroll, election systems, majority rule, completeness
12	Rolf H. Möhring, Matthias Müller-Hannemann, Karsten Weihe	Mesh refinement via bidirected flows: modeling, complexity, and computational results.	J. ACM	1997	DBLP DOI BibTeX RDF	b-matching problem, augmenting paths, bidirected flows, NP-completeness, templates, mesh generation
12	N. Raja 0001, R. K. Shyamasundar	Combinatory Formaulations of Concurrent Languages.	ACM Trans. Program. Lang. Syst.	1997	DBLP DOI BibTeX RDF	Quine-Bernays combinators, functional completeness
12	Ryuhei Uehara	A Measure of Parallelization for the Lexicographically First Maximal Subgraph Problems.	WG	1997	DBLP DOI BibTeX RDF	the lexicographically first maximal independent set problem, the lexicographically first maximal subgraph problems, Analysis of algorithms, P-completeness, NC algorithms
12	Bernhard Steffen	Unifying Models.	STACS	1997	DBLP DOI BibTeX RDF	(in-)completeness, (temporal) models, verification, architecture, temporal logic, refinement, abstraction, consistency, tools, process, operational semantics, partial evaluation, decidability, expressivity, transition system, behaviour, intermediate language
12	Christoph Karg	LR(k) Testing is Average Case Complete.	CCC	1997	DBLP DOI BibTeX RDF	Average Case Complexity, Average Case Completeness
12	Jack H. Lutz, Yong Zhao	The Density of Weakly Complete Problems under Adaptive Reductions.	CCC	1997	DBLP DOI BibTeX RDF	dense languages, polynomial reductions, sparse languages, weak completeness, computational complexity, complexity classes, resource-bounded measure
12	Chor Ping Low, Hon Wai Leong	A New Class of Efficient Algorithms for Reconfiguration of Memory Arrays.	IEEE Trans. Computers	1996	DBLP DOI BibTeX RDF	RRAMs, NP-completeness, throughput, heuristic algorithms, vertex covers, sparsity