Search results for "NP-hardness"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
2	Yan Gérard	About the Complexity of Timetables and 3-Dimensional Discrete Tomography: A Short Proof of NP-Hardness.	IWCIA	2009	DBLP DOI BibTeX RDF	Flow problems, NP-complete, Timetable, Discrete Tomography
2	Rong Ge, Martin Ester, Byron J. Gao, Zengjian Hu, Binay K. Bhattacharya, Boaz Ben-Moshe	Joint cluster analysis of attribute data and relationship data: The connected k-center problem, algorithms and applications.	TKDD	2008	DBLP DOI BibTeX RDF	Attribute data, joint cluster analysis, relationship data, approximation algorithms, NP-hardness, document clustering, community identification, market segmentation
2	Rong Ge, Martin Ester, Wen Jin, Ian Davidson	Constraint-driven clustering.	KDD	2007	DBLP DOI BibTeX RDF	clustering, constraints, NP-hardness
2	Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz	On basing one-way functions on NP-hardness.	STOC	2006	DBLP DOI BibTeX RDF	adaptive versus non-adaptive machines, reductions, one-way functions, interactive proof systems, average-case complexity
2	Guido Proietti, Peter Widmayer	Partitioning the Nodes of a Graph to Minimize the Sum of Subgraph Radii.	ISAAC	2006	DBLP DOI BibTeX RDF	Clustering problems, Graph radius, NP-hardness, Graph partition, Facility location problems
2	Guillaume Blin, Hélène Touzet	How to Compare Arc-Annotated Sequences: The Alignment Hierarchy.	SPIRE	2006	DBLP DOI BibTeX RDF	arc-annotated sequences, algorithm, NP-hardness, computational biology, edit distance, RNA structures
2	Ralf Klasing, Euripides Markou, Tomasz Radzik, Fabiano Sarracco	Hardness and Approximation Results for Black Hole Search in Arbitrary Graphs.	SIROCCO	2005	DBLP DOI BibTeX RDF	black hole search, approximation algorithm, mobile agent, NP-hardness, graph exploration
2	Bertrand M. T. Lin, T. C. Edwin Cheng	Two-Machine Flowshop Batching and Scheduling.	Annals OR	2005	DBLP DOI BibTeX RDF	strong NP-hardness, heuristics, lower bound, makespan, batch processing, production scheduling, flowshop
2	Thomas Erlebach, Alexander Hall	NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow.	J. Scheduling	2004	DBLP DOI BibTeX RDF	approximation algorithm, NP-complete, inapproximability, resource augmentation, broadcast scheduling
2	Davide Bilò, Guido Proietti	Augmenting the Edge-Connectivity of a Spider Tree.	ISAAC	2004	DBLP DOI BibTeX RDF	Edge-Connectivity Augmentation, Spider Tress, Graph Algorithms, NP-hardness, Network Survivability
2	Rolf Niedermeier	Ubiquitous Parameterization - Invitation to Fixed-Parameter Algorithms.	MFCS	2004	DBLP DOI BibTeX RDF	NP-hardness, parameterization, parameterized complexity, fixed-parameter algorithms
2	Bang Ye Wu	Constructing the Maximum Consensus Tree from Rooted Triples.	J. Comb. Optim.	2004	DBLP DOI BibTeX RDF	algorithms, dynamic programming, NP-hardness, computational biology, evolutionary trees
2	Wenci Yu, Han Hoogeveen, Jan Karel Lenstra	Minimizing Makespan in a Two-Machine Flow Shop with Delays and Unit-Time Operations is NP-Hard.	J. Scheduling	2004	DBLP DOI BibTeX RDF	intermediate delays, strong NP-hardness, computational complexity, makespan, flow shop scheduling
2	Thomas Eiter, Kazuhisa Makino	Generating All Abductive Explanations for Queries on Propositional Horn Theories.	CSL	2003	DBLP DOI BibTeX RDF	Horn theories, polynomial total time computation, NP-hardness, abduction, propositional logic, Computational logic
2	Thomas Eiter, Kazuhisa Makino	Abduction and the Dualization Problem.	Discovery Science	2003	DBLP DOI BibTeX RDF	monotone dualization, Horn functions, polynomial total-time computation, NP-hardness, Abduction, model-based reasoning, hypergraph transversals
2	Asa Packer	NP - Hardness of Largest Contained and Smallest Containing Simplices for V- and H-Polytopes.	Discrete & Computational Geometry	2002	DBLP DOI BibTeX RDF
2	Thomas Erlebach, Alexander Hall	NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow.	SODA	2002	DBLP DOI BibTeX RDF
2	Xiaodong Wu, Danny Z. Chen	Optimal Net Surface Problems with Applications.	ICALP	2002	DBLP DOI BibTeX RDF	3-D Image Segmentations, Algorithms, NP-hardness, Surface Reconstructions, Geometric Graphs
2	Rudi Pendavingh, Petra Schuurman, Gerhard J. Woeginger	De Bruijn Graphs and DNA Graphs.	WG	2001	DBLP DOI BibTeX RDF	De Bruijn graph, DNA graphs, computational complexity, graph theory, NP-hardness, DNA computing, recognition algorithm
2	Uriel Feige	Coping with the NP-Hardness of the Graph Bandwidth Problem.	SWAT	2000	DBLP DOI BibTeX RDF
2	Ming-Yang Kao, Jared Samet, Wing-Kin Sung	The Enhanced Double Digest Problem for DNA Physical Mapping.	SWAT	2000	DBLP DOI BibTeX RDF	graph-theoretic techniques, NP-hardness, fast algorithms, physical mapping
2	Sanghyun Ahn, David Hung-Chang Du	A Multicast Tree Algorithm Considering Maximum Delay Bound for Real-Time Applications. (PDF / PS)	LCN	1996	DBLP DOI BibTeX RDF	multicast tree algorithm, maximum delay bound, multiple multicast tree concept, tree maintenance cost, DBMT problem, shortest path tree-based DBMT, minimal Steiner tree-based DBMT, MST DBMT, SPT DBMT, performance analysis, group communication, NP-hardness, heuristic algorithms, real-time applications, multicast routing, telecommunication traffic, real-time traffic
2	Hemant D. Pande, William Landi, Barbara G. Ryder	Interprocedural Def-Use Associations for C Systems with Single Level Pointers.	IEEE Trans. Software Eng.	1994	DBLP DOI BibTeX RDF	interprocedural def-use associations, C software systems, single level pointers, value-setting statements, value-fetches, program-point-specific pointer-induced aliases, interprocedural reaching definitions problem, software engineering, computational complexity, data structures, static analysis, NP-hardness, program compilers, polynomial-time algorithm, program diagnostics, C language, indirection
1	Ying Xiao, Krishnaiyan Thulasiraman, Xi Fang, Dejun Yang, Guoliang Xue	Computing a Most Probable Delay Constrained Path: NP-Hardness and Approximation Schemes.	IEEE Trans. Computers	2012	DBLP DOI BibTeX RDF
1	Per Austrin, Ryan O'Donnell, John Wright	A new point of NP-hardness for 2-to-1 Label Cover	CoRR	2012	DBLP BibTeX RDF
1	Radoslaw Rudek	The strong NP-hardness of the maximum lateness minimization scheduling problem with the processing-time based aging effect.	Applied Mathematics and Computation	2012	DBLP DOI BibTeX RDF
1	Yuichi Asahiro, Kenichi Kawahara, Eiji Miyano	NP-hardness of the sorting buffer problem on the uniform metric.	Discrete Applied Mathematics	2012	DBLP DOI BibTeX RDF
1	Akshay Deepak, Jianrong Dong, David Fernández-Baca	Identifying Rogue Taxa through Reduced Consensus: NP-Hardness and Exact Algorithms.	ISBRA	2012	DBLP DOI BibTeX RDF
1	Ryan O'Donnell, John Wright	A new point of NP-hardness for unique games.	STOC	2012	DBLP DOI BibTeX RDF
1	Dana Moshkovitz	The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover.	Electronic Colloquium on Computational Complexity (ECCC)	2011	DBLP BibTeX RDF
1	Sushant Sachdeva, Rishi Saket	Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs	CoRR	2011	DBLP BibTeX RDF
1	Weiming Liu, Sanjiang Li	Reasoning about cardinal directions between extended objects: The NP-hardness result.	Artif. Intell.	2011	DBLP DOI BibTeX RDF
1	Sushant Sachdeva, Rishi Saket	Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs.	APPROX-RANDOM	2011	DBLP DOI BibTeX RDF
1	Subhash Khot, Dana Moshkovitz	NP-hardness of approximately solving linear equations over reals.	STOC	2011	DBLP DOI BibTeX RDF
1	Yong-Jin Liu, Wen-Qi Zhang, Kai Tang	Some notes on maximal arc intersection of spherical polygons: its NP\mathcal{NP} -hardness and approximation algorithms.	The Visual Computer	2010	DBLP DOI BibTeX RDF
1	Subhash Khot, Dana Moshkovitz	NP-Hardness of Approximately Solving Linear Equations Over Reals.	Electronic Colloquium on Computational Complexity (ECCC)	2010	DBLP BibTeX RDF
1	Sevag Gharibian	Strong NP-hardness of the quantum separability problem.	Quantum Information & Computation	2010	DBLP BibTeX RDF
1	Amir Ali Ahmadi, Alexander Olshevsky, Pablo A. Parrilo, John N. Tsitsiklis	NP-hardness of Deciding Convexity of Quartic Polynomials and Related Problems	CoRR	2010	DBLP BibTeX RDF
1	Mikhail Y. Kovalyov, Erwin Pesch	A generic approach to proving NP-hardness of partition type problems.	Discrete Applied Mathematics	2010	DBLP DOI BibTeX RDF
1	Elzbieta Roszkowska, Spiridon Reveliotis	Establishing the NP-hardness of maximally permissive RAS-based approaches to multi-vehicle system safety.	ICRA	2010	DBLP DOI BibTeX RDF
1	Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz	Erratum for: on basing one-way functions on NP-hardness.	STOC	2010	DBLP DOI BibTeX RDF
1	Florian Berger, Rolf Klein	A traveller's problem.	Symposium on Computational Geometry	2010	DBLP DOI BibTeX RDF	affine mappings, continuous dijkstra, frogger, pseudo-polynomial approximation, computational geometry, partition, np-hardness, motion planning, undecidability
1	Wei Yang, Weifa Liang, Jun Luo, Wenhua Dou	Energy-aware online routing with QoS constraints in multi-rate wireless ad hoc networks.	IWCMC	2010	DBLP DOI BibTeX RDF	energy-latency tradeoff, multi-rate ad hoc networks, network lifetime, QoS routing, energy optimization
1	Zhaonian Zou, Hong Gao, Jianzhong Li	Discovering frequent subgraphs over uncertain graph databases under probabilistic semantics.	KDD	2010	DBLP DOI BibTeX RDF	probabilistic semantics, uncertain graph, frequent subgraph
1	Matthew P. Johnson, Amotz Bar-Noy	Brief announcement: pan and scan.	PODC	2010	DBLP DOI BibTeX RDF	directional sensors, coverage, targets
1	Daniel Aloise, Amit Deshpande, Pierre Hansen, Preyas Popat	NP-hardness of Euclidean sum-of-squares clustering.	Machine Learning	2009	DBLP DOI BibTeX RDF
1	Georg Gottlob, Zoltán Miklós, Thomas Schwentick	Generalized hypertree decompositions: NP-hardness and tractable variants.	J. ACM	2009	DBLP DOI BibTeX RDF	TreeProjection Problem, hypertree decomposition, NP-complete, hypergraph, Conjunctive query, tractable, acyclic
1	Jianfeng Ren, Yuzhong Zhang, Guo Sun	The NP-Hardness of Minimizing the Total Late Work on an Unbounded Batch Machine.	APJOR	2009	DBLP DOI BibTeX RDF
1	Francisco J. Soulignac, Gabriel Sueiro	NP-hardness of the recognition of coordinated graphs.	Annals OR	2009	DBLP DOI BibTeX RDF
1	Victor Chepoi, Bernard Fichet, Morgan Seston	Seriation in the Presence of Errors: NP-Hardness of l INFINITY -Fitting Robinson Structures to Dissimilarity Matrices.	J. Classification	2009	DBLP DOI BibTeX RDF
1	Baoqiang Fan, Rongjun Chen, Guochun Tang	Bicriteria Scheduling on Single-Machine with Inventory Operations.	COCOA	2009	DBLP DOI BibTeX RDF	bicriteria, scheduling, approximation algorithm, NP-hardness, performance ratio
1	Yannis Smaragdakis, Christoph Csallner, Ranjith Subramanian	Scalable satisfiability checking and test data generation from modeling diagrams.	Autom. Softw. Eng.	2009	DBLP DOI BibTeX RDF	Modeling, Testing, Databases, NP-hardness, Test data generation, ORM, ORM-
1	Kazuo Iwama, Eiji Miyano, Hirotaka Ono	Drawing Borders Efficiently.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Algorithm, Approximation algorithm, Combinatorial optimization, NP-hardness, Spreadsheet
1	Alessandro Agnetis, Paolo Detti, Marco Pranzo, Manbir S. Sodhi	Sequencing unreliable jobs on parallel machines.	J. Scheduling	2009	DBLP DOI BibTeX RDF	Indexable problems, Unsupervised manufacturing systems, Approximation algorithms, NP-hardness, Polymatroids
1	Prakarn Unachak, Erik D. Goodman	Adaptive representation for flexible job-shop scheduling and rescheduling.	GEC Summit	2009	DBLP DOI BibTeX RDF	genetic algorithm, representation, rescheduling, flexible job shop scheduling problems
1	Frédéric Bihan, J. Maurice Rojas, Casey E. Stella	Faster real feasibility via circuit discriminants.	ISSAC	2009	DBLP DOI BibTeX RDF	discriminant chamber, linear forms in logarithms, real, polynomial-time, sparse, feasibility
1	Ruoming Jin, Yang Xiang, Lin Liu	Cartesian contour: a concise representation for a collection of frequent sets.	KDD	2009	DBLP DOI BibTeX RDF	concise pattern representation, frequent itemsets, set cover, cartesian product
1	Peng-Jun Wan	Multiflows in multihop wireless networks.	MobiHoc	2009	DBLP DOI BibTeX RDF	approximation algorithms, multicommodity flow, capacity region
1	Jian Li, Amol Deshpande	Consensus answers for queries over probabilistic databases.	PODS	2009	DBLP DOI BibTeX RDF	consensus answers, probabilistic and/xor tree, query processing, probabilistic databases, rank aggregation
1	Edith Elkind, Dmitrii V. Pasechnik	Computing the nucleolus of weighted voting games.	SODA	2009	DBLP DOI BibTeX RDF
1	Elad Hazan, Robert Krauthgamer	How hard is it to approximate the best Nash equilibrium?	SODA	2009	DBLP DOI BibTeX RDF
1	Jirí Matousek, Martin Tancer, Uli Wagner	Hardness of embedding simplicial complexes in Rd.	SODA	2009	DBLP DOI BibTeX RDF
1	Ryan O'Donnell, Yi Wu	3-bit dictator testing: 1 vs. 5/8.	SODA	2009	DBLP DOI BibTeX RDF
1	Madhur Tulsiani	CSP gaps and reductions in the lasserre hierarchy.	STOC	2009	DBLP DOI BibTeX RDF	constraint satisfaction, semidefinite programming, integrality gaps
1	Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe	The shield that never was: societies with single-peaked preferences are more open to manipulation and control.	TARK	2009	DBLP DOI BibTeX RDF
1	Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou	The complexity of computing a Nash equilibrium.	Commun. ACM	2009	DBLP DOI BibTeX RDF
1	Tim Nonner, Alexander Souza	Latency Constrained Aggregation in Chain Networks Admits a PTAS.	AAIM	2009	DBLP DOI BibTeX RDF
1	Gildas Jeantet, Olivier Spanjaard	Optimizing the Hurwicz Criterion in Decision Trees with Imprecise Probabilities.	ADT	2009	DBLP DOI BibTeX RDF	Hurwicz’s criterion, Computational complexity, Exact algorithms, Imprecise probabilities, Sequential decision making
1	Georg Gottlob, Gianluigi Greco, Zoltán Miklós, Francesco Scarcello, Thomas Schwentick	Tree Projections: Game Characterization and Computational Aspects.	Graph Theory, Computational Intelligence and Thought	2009	DBLP DOI BibTeX RDF	tree projections, computational complexity, hypergraphs
1	Andreas Karrenbauer	Matching Techniques Ride to Rescue OLED Displays.	COCOA	2009	DBLP DOI BibTeX RDF
1	Sebastian Böcker, Quang Bao Anh Bui, Patrick Seeber, Anke Truß	Computing Bond Types in Molecule Graphs.	COCOON	2009	DBLP DOI BibTeX RDF
1	Iyad A. Kanj, Dieter Kratsch	Convex Recoloring Revisited: Complexity and Exact Algorithms.	COCOON	2009	DBLP DOI BibTeX RDF
1	Davide Bilò, Hans-Joachim Böckenhauer, Dennis Komm, Richard Královic, Tobias Mömke, Sebastian Seibert, Anna Zych	Reoptimization of the Shortest Common Superstring Problem.	CPM	2009	DBLP DOI BibTeX RDF
1	Christian Komusiewicz, Rolf Niedermeier, Johannes Uhlmann	Deconstructing Intractability: A Case Study for Interval Constrained Coloring.	CPM	2009	DBLP DOI BibTeX RDF
1	Refael Hassin, R. Ravi, F. Sibel Salman	Tractable Cases of Facility Location on a Network with a Linear Reliability Order of Links.	ESA	2009	DBLP DOI BibTeX RDF
1	Michael A. Bender, Sándor P. Fekete, Tom Kamphans, Nils Schweer	Maintaining Arrays of Contiguous Objects.	FCT	2009	DBLP DOI BibTeX RDF
1	Jinhee Chun, Ryosei Kasai, Matias Korman, Takeshi Tokuyama	Algorithms for Computing the Maximum Weight Region Decomposable into Elementary Shapes.	ISAAC	2009	DBLP DOI BibTeX RDF
1	Hao Rao, Lining Xing	Dynamic Structure-Based Neural Networks Determination Approach Based on the Orthogonal Genetic Algorithm with Quantization.	ISNN	2009	DBLP DOI BibTeX RDF	DSNN, Neural networks
1	Nadja Betzler, Britta Dorn	Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules.	MFCS	2009	DBLP DOI BibTeX RDF
1	Yixiang Chen, Min Zhang, Hong Zhu, Tian-Ming Bu	Average Transitive Trustworthy Degrees for Trustworthy Networks.	RSKT	2009	DBLP DOI BibTeX RDF
1	Martin Hoefer, Lars Olbrich, Alexander Skopalik	Doing Good with Spam Is Hard.	SAGT	2009	DBLP DOI BibTeX RDF
1	Laurent Gourvès, Adria Lyra, Carlos A. J. Martinhon, Jérôme Monnot	The Minimum Reload s-tPath/Trail/Walk Problems.	SOFSEM	2009	DBLP DOI BibTeX RDF
1	Mathias Weller, Christian Komusiewicz, Rolf Niedermeier, Johannes Uhlmann	On Making Directed Graphs Transitive.	WADS	2009	DBLP DOI BibTeX RDF
1	Michael Bauland, Edith Hemaspaandra	Isomorphic Implication.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Computational complexity, Constraints, Propositional logic, Logic in computer science, Isomorphism problem
1	Matthias Müller-Hannemann, Alexander Sonnikow	Non-approximability of just-in-time scheduling.	J. Scheduling	2009	DBLP DOI BibTeX RDF	Earliness, Non-approximability, Special cases, Single machine scheduling, Just-in-time, Tardiness
1	Samuel R. Buss, Jan Hoffmann 0002	The NP-hardness of finding a directed acyclic graph for regular resolution.	Theor. Comput. Sci.	2008	DBLP DOI BibTeX RDF
1	Olivier Hudry	NP-hardness results for the aggregation of linear orders into median orders.	Annals OR	2008	DBLP DOI BibTeX RDF	Partially ordered relations, Median relations, Aggregation of preferences, Complexity
1	Zhi Xu, Jeffrey Shallit	An NP-hardness Result on the Monoid Frobenius Problem	CoRR	2008	DBLP BibTeX RDF
1	Yuichi Asahiro, Kenichi Kawahara, Eiji Miyano	NP-Hardness of the Sorting Buffer Problem on the Uniform Metric.	FCS	2008	DBLP BibTeX RDF
1	Ken Been, Martin Nöllenburg, Sheung-Hung Poon, Alexander Wolff	Optimizing active ranges for consistent dynamic map labeling.	Symposium on Computational Geometry	2008	DBLP DOI BibTeX RDF	dynamic map labeling, approximation algorithms, np-hardness
1	Minzhu Xie, Jianxin Wang, Jianer Chen	A Practical Exact Algorithm for the Individual Haplotyping Problem MEC.	BMEI	2008	DBLP DOI BibTeX RDF	SNP (single-nucleotide polymorphism), MEC (Minimum Error Correction), NP-hardness, haplotype
1	Richard Matthew McCutchen	The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences.	LATIN	2008	DBLP DOI BibTeX RDF	one-sided preferences, popular matching, algorithms, matching, NP-hardness, voting
1	Minzhu Xie, Jianxin Wang, Jianer Chen	A Practical Parameterized Algorithm for the Individual Haplotyping Problem MLF.	TAMC	2008	DBLP DOI BibTeX RDF	SNP (single-nucleotide polymorphism), MLF (Minimum Letter Flip), NP-hardness, haplotype, parameterized algorithm
1	Yerim Chung, Jean-François Culus, Marc Demange	Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs.	WALCOM	2008	DBLP DOI BibTeX RDF	Inverse combinatorial optimization, Inverse chromatic number problem, Machine(s)-scheduling with earliness and or tardiness costs, Approximation, NP-hardness, Interval graphs
1	Davide Bilò, Luca Forlizzi, Guido Proietti	Approximating the Metric TSP in Linear Time.	WG	2008	DBLP DOI BibTeX RDF	Metric Graphs, Linear-time Approximation Algorithms, NP-hardness, Traveling Salesman Problem
1	Minzhu Xie, Jianxin Wang	An Improved (and Practical) Parameterized Algorithm for the Individual Haplotyping Problem MFR with Mate-Pairs.	Algorithmica	2008	DBLP DOI BibTeX RDF	SNP (single-nucleotide polymorphism), NP-hardness, Haplotype, Genotype, Parameterized algorithm
1	Ling Gai, Guochuan Zhang	On lazy bureaucrat scheduling with common deadlines.	J. Comb. Optim.	2008	DBLP DOI BibTeX RDF	Sheduling, NP-hardness, Approximation scheme
1	Guoli Ding, Li Feng, Wenan Zang	The complexity of recognizing linear systems with certain integrality properties.	Math. Program.	2008	DBLP DOI BibTeX RDF	Total dual integrality, NP-hardness, Linear system, Polyhedron
1	Marjan van den Akker, Han Hoogeveen	Minimizing the number of late jobs in a stochastic setting using a chance constraint.	J. Scheduling	2008	DBLP DOI BibTeX RDF	Number of late jobs, Stochastic processing times, Minimum success probability, Chance constraint, Scheduling, Dynamic programming, NP-hardness, Sequencing, Single machine
1	Giorgio Ghelli, Dario Colazzo, Carlo Sartiani	Linear time membership in a class of regular expressions with interleaving and counting.	CIKM	2008	DBLP DOI BibTeX RDF	xml, regular expressions, xml schema