Search results for "NP-hard"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
14	Sandip Aine, Rajeev Kumar 0004, P. P. Chakrabarti 0001	An Adaptive Framework for Solving Multiple Hard Problems Under Time Constraints.	CIS (1)	2005	DBLP DOI BibTeX RDF
14	Jun Li, Fumin Yang, Yansheng Lu	A Feasible Schedulability Analysis for Fault-Tolerant Hard Real-Time Systems.	ICECCS	2005	DBLP DOI BibTeX RDF
14	Vishnu Swaminathan, Krishnendu Chakrabarty	Network flow techniques for dynamic voltage scaling in hard real-time systems.	IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.	2004	DBLP DOI BibTeX RDF
14	Jozef Chovan, Frantisek Uherek	Modification of Decoder for 2-D Wavelength/Time Optical CDMA System by Optical Hard-Limiters.	OpNeTec	2004	DBLP DOI BibTeX RDF
14	Daniel L. Dvorak, William K. Reinholtz	Hard real-time: C++ versus RTSJ.	OOPSLA Companion	2004	DBLP DOI BibTeX RDF	real-time, architecture, concurrency, programming model
14	Luis Alejandro Cortés, Petru Eles, Zebo Peng	Quasi-Static Scheduling for Real-Time Systems with Hard and Soft Tasks.	DATE	2004	DBLP DOI BibTeX RDF
14	Christo Angelov, Jesper Berthing	A Jitter-Free Kernel for Hard Real-Time Systems.	ICESS	2004	DBLP DOI BibTeX RDF
14	Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel	All Superlinear Inverse Schemes Are coNP-Hard.	MFCS	2004	DBLP DOI BibTeX RDF
14	Kavitha S. Golconda, Atakan Dogan, Füsun Özgüner	Static Mapping Heuristics for Tasks with Hard Deadlines in Real-Time Heterogeneous Systems.	ISCIS	2004	DBLP DOI BibTeX RDF
14	Jork Löser, Hermann Härtig	Using Switched Ethernet for Hard Real-Time Communication.	PARELEC	2004	DBLP DOI BibTeX RDF	Real Time Parallel Computing
14	Haixia Jia, Cristopher Moore, Bart Selman	From Spin Glasses to Hard Satisfiable Formulas.	SAT (Selected Papers	2004	DBLP DOI BibTeX RDF
14	Frédéric Ridouard, Pascal Richard, Francis Cottet	Negative Results for Scheduling Independent Hard Real-Time Tasks with Self-Suspensions.	RTSS	2004	DBLP DOI BibTeX RDF
14	Christoph Ambühl, Birgitta Weber	Parallel Prefetching and Caching Is Hard.	STACS	2004	DBLP DOI BibTeX RDF
14	Nitin Auluck, Dharma P. Agrawal	An Integrated Scheduling Algorithm for Precedence Constrained Hard and Soft Real-Time Tasks on Heterogeneous Multiprocessors.	EUC	2004	DBLP DOI BibTeX RDF
14	Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, Ge Xia	Tight Lower Bounds for Certain Parameterized NP-Hard Problems.	CCC	2004	DBLP DOI BibTeX RDF
14	Vishnu Swaminathan, Krishnendu Chakrabarty	Energy-conscious, deterministic I/O device scheduling in hard real-time systems.	IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.	2003	DBLP DOI BibTeX RDF
14	Han-Saem Yun, Jihong Kim 0001	On energy-optimal voltage scheduling for fixed-priority hard real-time systems.	ACM Trans. Embed. Comput. Syst.	2003	DBLP DOI BibTeX RDF	real-time systems, approximation algorithms, dynamic voltage scaling, Fixed-priority scheduling, fully polynomial time approximation scheme, variable voltage processor
14	Irith Pomeranz, Sudhakar M. Reddy, Sandip Kundu	On the Characterization of Hard-to-Detect Bridging Faults.	DATE	2003	DBLP DOI BibTeX RDF
14	Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan	An Improved Approximation Algorithm for Vertex Cover with Hard Capacities.	ICALP	2003	DBLP DOI BibTeX RDF	capacitated covering, Approximation algorithms, linear programming, set cover, vertex cover, randomized rounding
14	Yoonmee Doh, Daeyoung Kim 0001, Yann-Hang Lee, C. Mani Krishna 0001	Constrained Energy Allocation for Mixed Hard and Soft Real-Time Tasks.	RTCSA	2003	DBLP DOI BibTeX RDF
14	Dag Nyström, Aleksandra Tesanovic, Christer Norström, Jörgen Hansson	Database Pointers: A Predictable Way of Manipulating Hot Data in Hard Real-Time Systems.	RTCSA	2003	DBLP DOI BibTeX RDF
14	Vishnu Swaminathan, Krishnendu Chakrabarty	Generalized Network Flow Techniques for Dynamic Voltage Scaling in Hard Real-Time Systems.	ICCAD	2003	DBLP DOI BibTeX RDF
14	Luis von Ahn, Manuel Blum 0001, Nicholas J. Hopper, John Langford 0001	CAPTCHA: Using Hard AI Problems for Security.	EUROCRYPT	2003	DBLP DOI BibTeX RDF
14	Seiichi Nishihara, Kazunori Mizuno, Kohsuke Nishihara	A Composition Algorithm for Very Hard Graph 3-Colorability Instances.	CP	2003	DBLP DOI BibTeX RDF
14	Jan Gustafsson, Björn Lisper, Raimund Kirner, Peter P. Puschner	Input-Dependency Analysis for Hard Real-Time Software.	WORDS Fall	2003	DBLP DOI BibTeX RDF
14	Mark Cieliebak, Stephan J. Eidenbenz, Paolo Penna	Noisy Data Make the Partial Digest Problem NP-hard.	WABI	2003	DBLP DOI BibTeX RDF
14	Detlef Sieling	Minimization of Decision Trees Is Hard to Approximate.	CCC	2003	DBLP DOI BibTeX RDF
14	Subhash Khot, Oded Regev 0001	Vertex Cover Might be Hard to Approximate to within 2-\varepsilon.	CCC	2003	DBLP DOI BibTeX RDF
14	Anbulagan, John Thornton 0001, Abdul Sattar 0001	Dynamic Variable Filtering for Hard Random 3-SAT Problems.	Australian Conference on Artificial Intelligence	2003	DBLP DOI BibTeX RDF	Search, Constraints, Problem Solving
14	Vladik Kreinovich	Range Estimation Is NP-Hard for ?2 Accuracy and Feasible for epsilon2-[delta].	Reliab. Comput.	2002	DBLP DOI BibTeX RDF
14	René Sitters	The Minimum Latency Problem Is NP-Hard for Weighted Trees.	IPCO	2002	DBLP DOI BibTeX RDF
14	Bruno Caprile, Cesare Furlanello, Stefano Merler	Highlighting Hard Patterns via AdaBoost Weights Evolution.	Multiple Classifier Systems	2002	DBLP DOI BibTeX RDF
14	Srikanth Ramamurthy	Scheduling Periodic Hard Real-Time Tasks with Arbitrary Deadlines on Multiprocessors.	RTSS	2002	DBLP DOI BibTeX RDF
14	Jirí Srba	Strong Bisimilarity and Regularity of Basic Parallel Processes Is PSPACE-Hard.	STACS	2002	DBLP DOI BibTeX RDF
14	Woonseok Kim, Dongkun Shin, Han-Saem Yun, Jihong Kim 0001, Sang Lyul Min	Performance Comparison of Dynamic Voltage Scaling Algorithms for Hard Real-Time Systems.	IEEE Real Time Technology and Applications Symposium	2002	DBLP DOI BibTeX RDF
14	Ole Martin Halck	Using Hard Classifiers to Estimate Conditional Class Probabilities.	ECML	2002	DBLP DOI BibTeX RDF
14	Jinghuan Chen, Jaekyun Moon, Kia Bazargan	A reconfigurable FPGA-based readback signal generator for hard-drive read channel simulator.	DAC	2002	DBLP DOI BibTeX RDF
14	Julio L. Medina, J. Javier Gutiérrez, José M. Drake, Michael González Harbour	Modeling and Schedulability Analysis of Hard Real-Time Distributed Systems Based on Ada Components.	Ada-Europe	2002	DBLP DOI BibTeX RDF
14	Ian Broster, Alan Burns 0001	Timely Use of the CAN Protocol in Critical Hard Real-Time Systems with Faults.	ECRTS	2001	DBLP DOI BibTeX RDF
14	Vishnu Swaminathan, Krishnendu Chakrabarty	Investigating the effect of voltage-switching on low-energy task scheduling in hard real-time systems.	ASP-DAC	2001	DBLP DOI BibTeX RDF
14	Jirí Síma	Minimizing the Quadratic Training Error of a Sigmoid Neuron Is Hard.	ALT	2001	DBLP DOI BibTeX RDF
14	Jean-Philippe Dubernard, Dominique Geniet	Scheduling Hard Sporadic Tasks by Means of Finite Automata and Generating Functions.	CIAA	2001	DBLP DOI BibTeX RDF
14	José María Álvarez 0002, Manuel Díaz, Luis Llopis, Ernesto Pimentel 0001, José M. Troya	Deriving hard real-time embedded systems implementations directly from SDL specifications.	CODES	2001	DBLP DOI BibTeX RDF	scheduler, embedded system, real-time, SDL
14	Vishnu Swaminathan, Krishnendu Chakrabarty, S. Sitharama Iyengar	Dynamic I/O power management for hard real-time systems.	CODES	2001	DBLP DOI BibTeX RDF
14	Adam L. Young, Moti Yung	A PVSS as Hard as Discrete Log and Shareholder Separability.	Public Key Cryptography	2001	DBLP DOI BibTeX RDF
14	Xavier Muñoz, Walter Unger, Imrich Vrto	One Sided Crossing Minimization Is NP-Hard for Sparse Graphs.	GD	2001	DBLP DOI BibTeX RDF
14	Wynne Hsu, P. M. D. S. Pallawala, Mong-Li Lee, Kah-Guan Au Eong	The Role of Domain Knowledge in the Detection of Retinal Hard Exudates.	CVPR (2)	2001	DBLP DOI BibTeX RDF
14	Christophe Costa Florêncio	Consistent Identification in the Limit of Any of the Classes k -Valued Is NP-hard.	LACL	2001	DBLP DOI BibTeX RDF	Learning theory, Grammatical inference, Categorial grammars, Formal language theory
14	Hans-Joachim Böckenhauer, Juraj Hromkovic, Ralf Klasing, Sebastian Seibert, Walter Unger	Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem.	CIAC	2000	DBLP DOI BibTeX RDF
14	Vikraman Arvind, Johannes Köbler, Martin Mundhenk, Jacobo Torán	Nondeterministic Instance Complexity and Hard-to-Prove Tautologies.	STACS	2000	DBLP DOI BibTeX RDF
14	Andrés Terrasa, Ana García-Fornes	Real-Time Synchronization Between Hard and Soft Tasks in RT-Linux.	RTCSA	1999	DBLP DOI BibTeX RDF	real-time synchronization, real-time operating systems, priority inheritance
14	Thomas Toifl, Paulo Moreira	A radiation-hard 80 MHz phase locked loop for clock and data recovery.	ISCAS (2)	1999	DBLP DOI BibTeX RDF
14	Giovanni Jacovitti, Alessandro Neri 0001, Gaetano Scarano	Texture synthesis-by-analysis with hard-limited Gaussian processes.	IEEE Trans. Image Process.	1998	DBLP DOI BibTeX RDF
14	Thomas Kolloch, Georg Färber	Mapping an Embedded Hard Real-Time Systems SDL Specification to an Analyzable Task Network - A Case Study.	LCTES	1998	DBLP DOI BibTeX RDF
14	Bharat P. Dave, Niraj K. Jha	CASPER: Concurrent Hardware-Software Co-Synthesis of Hard Real-Time Aperiodic and Periodic Specifications of Embedded System Architectures.	DATE	1998	DBLP DOI BibTeX RDF	aperiodic task graphs, scheduling, distributed systems, embedded systems, allocation, system synthesis, hardware-software co-synthesis
14	Agustín Espinosa, Vicente Julián, Carlos Carrascosa, Andrés Terrasa, Ana García-Fornes	Programming Hard Real-Time Systems with Optional Components in Ada.	Ada-Europe	1998	DBLP DOI BibTeX RDF
14	Michael González Harbour, Mario Aldea Rivas, J. J. Gutiérrez García, José C. Palencia Gutiérrez	Implementing and Using Execution Time Clocks in Ada Hard Real-Time Applications.	Ada-Europe	1998	DBLP DOI BibTeX RDF
14	Christian Höhn, Colin R. Reeves	Are Long Path Problems Hard for Genetic Algorithms?	PPSN	1996	DBLP DOI BibTeX RDF
14	Rainer E. Burkard, Eranda Çela, Günter Rote, Gerhard J. Woeginger	The Quadratic Assignment Problem with a Monotone Anti-Monge and a Symmetric Toeplitz Matrix: Easy and Hard Cases.	IPCO	1996	DBLP DOI BibTeX RDF
14	Yasuhiro Kokusho, Norihisa Doi	Scheduling hard-realtime parallel tasks onto the processor network with wrapped mesh topology.	RTCSA	1995	DBLP DOI BibTeX RDF	realtime parallel tasks, wrapped mesh topology, load-distribution mechanism, Double-Layered Load-Distribution, DLLD, scheduling, real-time systems, parallel processing, parallel computing, resource allocation, multiprocessing systems, multiprocessor systems, processor scheduling
14	Wing Ning	Strongly NP-hard discrete gate-sizing problems.	IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.	1994	DBLP DOI BibTeX RDF
14	Joseph Kee-Yin Ng, Jane W.-S. Liu	Performance of local area network protocols for hard real-time applications.	ICDCS	1991	DBLP DOI BibTeX RDF
14	Maryline Silly, Houssine Chetto, N. Elyounsi	An optimal algorithm for guaranteeing sporadic tasks in hard real-time systems.	SPDP	1990	DBLP DOI BibTeX RDF
14	Uwe Schöning	Complexity Cores and Hard Problem Instances.	SIGAL International Symposium on Algorithms	1990	DBLP DOI BibTeX RDF
14	Abha Moitra	Scheduling of Hard Real-Time Systems.	FSTTCS	1986	DBLP DOI BibTeX RDF	pre-emptive, real-time systems, Deadline, scheduling policy, rate-monotonic
14	David Lichtenstein, Michael Sipser	GO Is Polynomial-Space Hard.	J. ACM	1980	DBLP DOI BibTeX RDF
14	Albrecht Schmidt 0001	Engineering interactive ubiquitous computing systems.	EICS	2011	DBLP DOI BibTeX RDF
14	Hasan Guclu, Murat Yuksel	Limited Scale-Free Overlay Topologies for Unstructured Peer-to-Peer Networks.	IEEE Trans. Parallel Distributed Syst.	2009	DBLP DOI BibTeX RDF
14	Rudi Cilibrasi, Leo van Iersel, Steven Kelk, John Tromp	The Complexity of the Single Individual SNP Haplotyping Problem.	Algorithmica	2007	DBLP DOI BibTeX RDF
14	Sadik Kara, Pinar Özel	Determination of Effects of Different Music on Frontal Muscle by Using EMG Signal.	FBIT	2007	DBLP DOI BibTeX RDF	Music Therapy Welch Method, Frontalis Eletromyography, Music
14	Jai Wug Kim, Jongpil Lee, Heon Young Yeom	Experimental Assessment of the Practicality of a Fault-Tolerant System.	SOFSEM (1)	2007	DBLP DOI BibTeX RDF
14	Hyuck Han, Jai Wug Kim, Jongpil Lee, Youngjin Yu, Kiyoung Kim, Heon Young Yeom	Practical Fault-Tolerant Framework for eScience Infrastructure.	e-Science	2006	DBLP DOI BibTeX RDF
14	Emanuele Viola	On Constructing Parallel Pseudorandom Generators from One-Way Functions.	CCC	2005	DBLP DOI BibTeX RDF	Pseudorandom generator construction, one-way function, black-box, restriction, constant-depth circuit, noise sensitivity, hardness amplification
14	Miguel Masmano, Jorge Real, Alfons Crespo, Ismael Ripoll	Distributing Criticality Across Ada Partitions.	Ada-Europe	2005	DBLP DOI BibTeX RDF
14	Emanuele Viola	Hardness vs. Randomness within Alternating Time.	CCC	2003	DBLP DOI BibTeX RDF
14	Subhash Khot	On the power of unique 2-prover 1-round games.	STOC	2002	DBLP DOI BibTeX RDF
14	Subhash Khot	On the Power of Unique 2-Prover 1-Round Games.	CCC	2002	DBLP DOI BibTeX RDF	2-prover games, Hardness of approximation, probabilistically checkable proofs
14	Ian Agol, Joel Hass, William P. Thurston	3-MANIFOLD KNOT GENUS is NP-complete.	CCC	2002	DBLP DOI BibTeX RDF	2-prover games, Hardness of approximation, probabilistically checkable proofs
14	Antonín Kucera 0001	On Simulation-Checking with Sequential Systems.	ASIAN	2000	DBLP DOI BibTeX RDF
14	Eric A. Brewer	Towards robust distributed systems (abstract).	PODC	2000	DBLP DOI BibTeX RDF
11	Phillip A. Laplante	Ender Wiggin Played Mafia Wars Too.	IT Prof.	2011	DBLP DOI BibTeX RDF	surreptitious problem solving, social networks, information technology, NP-complete problems, NP-hard problems, crowdsourcing, Gameplay
11	Ling Ding, Weili Wu 0001, James Willson, Hongjie Du, Wonjun Lee 0001, Ding-Zhu Du	Efficient Algorithms for Topology Control Problem with Routing Cost Constraints in Wireless Networks.	IEEE Trans. Parallel Distributed Syst.	2011	DBLP DOI BibTeX RDF	routing path, wireless network, NP-hard, topology control, Connected dominating set, obstacle, general graph
11	Jorge Crichigno, Min-You Wu, Sudharman K. Jayaweera, Wei Shu	Throughput Optimization in Multihop Wireless Networks with Multipacket Reception and Directional Antennas.	IEEE Trans. Parallel Distributed Syst.	2011	DBLP DOI BibTeX RDF	Wireless networks, NP-hard, directional antennas, multihop, multipacket reception
11	Omer Khan, Sandip Kundu	Hardware/Software Codesign Architecture for Online Testing in Chip Multiprocessors.	IEEE Trans. Dependable Secur. Comput.	2011	DBLP DOI BibTeX RDF	hard error detection, isolation and tolerance, Chip Multiprocessor (CMP), hardware/software codesign
11	Frederick T. Sheldon, Claire Vishik	Moving Toward Trustworthy Systems: R&D Essentials.	Computer	2010	DBLP DOI BibTeX RDF	Trustworthy systems, R&D essentials, Game-change metaphors, Hard-problem strategies
11	Mahboobeh Houshmand, Elaheh Soleymanpour, Hossein Salami, Mahya Amerian, Hossein Deldari	Efficient Scheduling of Task Graphs to Multiprocessors Using a Combination of Modified Simulated Annealing and List Based Scheduling.	IITSI	2010	DBLP DOI BibTeX RDF	List based scheduling algorithms, modified simulated annealing, task scheduling problem, NP hard problems
11	Senjuti Basu Roy, Sihem Amer-Yahia, Ashish Chawla, Gautam Das 0001, Cong Yu 0001	Constructing and exploring composite items.	SIGMOD Conference	2010	DBLP DOI BibTeX RDF	composite item construction, np-hard problems, e-commerce application
11	Feng Wu, Peiwen Yu	Theoretically Optimal Low-Density Parity-Check Code Ensemble for Gallager's Decoding Algorithm A.	DCC	2010	DBLP DOI BibTeX RDF	hard decision, LDPC, code design
11	Jörg Mische, Sascha Uhrig, Florian Kluge, Theo Ungerer	Using SMT to Hide Context Switch Times of Large Real-Time Tasksets.	RTCSA	2010	DBLP DOI BibTeX RDF	hardware scheduler, in-order multithreading, hard real-time, SMT, context switch
11	Feng Chen 0005, Xiaodong Zhang 0001	PS-BC: power-saving considerations in design of buffer caches serving heterogeneous storage devices.	ISLPED	2010	DBLP DOI BibTeX RDF	power management, energy saving, buffer caches, hard disk
11	Jack Whitham, Neil C. Audsley	Studying the Applicability of the Scratchpad Memory Management Unit.	IEEE Real-Time and Embedded Technology and Applications Symposium	2010	DBLP DOI BibTeX RDF	Embedded Hard Real-time, WCET, Scratchpad
11	Ling Ding, Xiaofeng Gao 0001, Weili Wu 0001, Wonjun Lee 0001, Xu Zhu, Ding-Zhu Du	Distributed Construction of Connected Dominating Sets with Minimum Routing Cost in Wireless Networks.	ICDCS	2010	DBLP DOI BibTeX RDF	wireless networks, shortest path, NP-hard, Connected dominating set, obstacle, virtual backbones, general graph
11	Laura Raya, Susana Mata, Óscar D. Robles	Perceptual evaluation of illumination effects in virtual environments.	APGV	2010	DBLP DOI BibTeX RDF	hard shadow, perception, reflections, soft shadow
11	Thorsten Zitterell, Christoph Scholl 0001	A probabilistic and energy-efficient scheduling approach for online application in real-time systems.	DAC	2010	DBLP DOI BibTeX RDF	dynamic voltage scaling, hard real-time, energy-aware scheduling
11	Les R. Foulds, Horst W. Hamacher	Facilities Layout Problems.	Encyclopedia of Optimization	2009	DBLP DOI BibTeX RDF	Multifacilities location, REL chart scores, Improved procedure, Construction procedures, Planar subgraph, Multicriteria objective function, Transportation cost, Layout manager, Genetic algorithms, Graph theory, Heuristics, Simulated annealing, Graph, Decision support system, Integer programming, Location, NP-hard, Branch and bound, Lagrangian relaxation, Bounds, Quadratic assignment problem, Adjacency graph
11	Sanatan Rai, George L. 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
11	Hamilton Emmons, Sanatan Rai	Computational Complexity Theory.	Encyclopedia of Optimization	2009	DBLP DOI BibTeX RDF	Recognition problem, Time complexity function, Nondeterministic polynomial algorithm, Computational complexity, Combinatorial optimization, Reducibility, NP-complete problem, Efficient algorithm, Complexity theory, NP-hard problem, Polynomial algorithm, Decision problem, Exponential algorithm
11	Horst W. Hamacher, Stefan Nickel	Multifacility and Restricted Location Problems.	Encyclopedia of Optimization	2009	DBLP DOI BibTeX RDF	Weber problem, Weber-Rawls problem, multifacility Weber problem, multiWeber problem, Gauge, Restricted location problem, Finite dominating set, Barrier location problems, Linear programming, Voronoi diagram, NP-hard, Discretization, Convex polytope, Location theory
11	Stephen A. Vavasis	Complexity Theory.	Encyclopedia of Optimization	2009	DBLP DOI BibTeX RDF	Information-based complexity, Real number model, Complexity, NP-complete, NP-hard, Polynomial time, Turing machine, Decision problem
11	Stephen A. Vavasis	Complexity Theory: Quadratic Programming.	Encyclopedia of Optimization	2009	DBLP DOI BibTeX RDF	Trust region problem, Strongly polynomial time, Simplicial constraints, Box constraints, Ellipsoid method, Approximation algorithms, Complexity, NP-complete, NP-hard, Quadratic programming, Polynomial time, Knapsack problem, Interior point methods, Local minimization