Search results for "tractability"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
155	Erich Novak, Ian H. Sloan, Henryk Wozniakowski	Tractability of Approximation for Weighted Korobov Spaces on Classical and Quantum Computers.	Found. Comput. Math.	2004	DBLP DOI BibTeX RDF	Korobov spaces, Approximation, Randomized algorithms, Quantum computation, Tractability
92	Michael Gnewuch, Henryk Wozniakowski	Generalized Tractability for Multivariate Problems Part II: Linear Tensor Product Problems, Linear Information, and Unrestricted Tractability.	Found. Comput. Math.	2009	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 65D99
63	Fedor V. Fomin, Saket Saurabh 0001	Kernelization Methods for Fixed-Parameter Tractability.	Tractability	2014	DBLP DOI BibTeX RDF
63	Nikolaj S. Bjørner, Leonardo Mendonça de Moura	Tractability and Modern Satisfiability Modulo Theories Solvers.	Tractability	2014	DBLP DOI BibTeX RDF
63	Rodney G. Downey, Martin Grohe, Gerhard J. Woeginger	05301 Summary - Exact Algorithms and Fixed-Parameter Tractability.	Exact Algorithms and Fixed-Parameter Tractability	2005	DBLP BibTeX RDF
63	Rodney G. Downey, Martin Grohe, Gerhard J. Woeginger	05301 Abstracts Collection - Exact Algorithms and Fixed-Parameter Tractability.	Exact Algorithms and Fixed-Parameter Tractability	2005	DBLP BibTeX RDF
59	Fred J. Hickernell, Henryk Wozniakowski	Integration and approximation in arbitrary dimensions.	Adv. Comput. Math.	2000	DBLP DOI BibTeX RDF	curse of dimension, multivariate integration, multivariate approximation, 65D05, 41A63, tractability, 41A05, 41A25
47	Suvrit Sra	Tractable Optimization in Machine Learning.	Tractability	2014	DBLP DOI BibTeX RDF
47	Lara Dolecek	Towards Practical Graph-Based, Iteratively Decoded Channel Codes: Insights through Absorbing Sets.	Tractability	2014	DBLP DOI BibTeX RDF
47	Pushmeet Kohli	Efficient Submodular Function Minimization for Computer Vision.	Tractability	2014	DBLP DOI BibTeX RDF
47	Tony Jebara	Perfect Graphs and Graphical Modeling.	Tractability	2014	DBLP DOI BibTeX RDF
47	João Marques-Silva 0001, Inês Lynce	SAT Solvers.	Tractability	2014	DBLP DOI BibTeX RDF
47	Andreas Krause 0001, Daniel Golovin	Submodular Function Maximization.	Tractability	2014	DBLP DOI BibTeX RDF
47	Adnan Darwiche	Tractable Knowledge Representation Formalisms.	Tractability	2014	DBLP DOI BibTeX RDF
47	Mohit Singh, Kunal Talwar	Approximation Algorithms.	Tractability	2014	DBLP DOI BibTeX RDF
47	Georg Gottlob, Gianluigi Greco, Francesco Scarcello	Treewidth and Hypertree Width.	Tractability	2014	DBLP DOI BibTeX RDF
47		Introduction.	Tractability	2014	DBLP DOI BibTeX RDF
47	Vladimir Kolmogorov	Tree-Reweighted Message Passing.	Tractability	2014	DBLP DOI BibTeX RDF
47	Peter G. Jeavons, Stanislav Zivný	Tractable Valued Constraints.	Tractability	2014	DBLP DOI BibTeX RDF
47	Rodney G. Downey, Martin Grohe, Gerhard J. Woeginger (eds.)	Exact Algorithms and Fixed-Parameter Tractability, 24.-27. July 2005	Exact Algorithms and Fixed-Parameter Tractability	2006	DBLP BibTeX RDF
46	Tuan Zea Tan, Geok See Ng, Chai Quek	Improving tractability of Clinical Decision Support system.	IJCNN	2008	DBLP DOI BibTeX RDF
44	Roded Sharan, Bjarni V. Halldórsson, Sorin Istrail	Islands of Tractability for Parsimony Haplotyping.	CSB	2005	DBLP DOI BibTeX RDF	approximation algorithm, complexity, fixed parameter tractability, genotype, parsimony, Haplotype inference
38	Thomas Eiter, Kazuhisa Makino	On computing all abductive explanations from a propositional Horn theory.	J. ACM	2007	DBLP DOI BibTeX RDF	Horn theories, dualization problem, polynomial total-time computation, NP-hardness, Abduction, model-based reasoning, propositional logic, tractability, prime implicates, characteristic set, enumeration algorithms
38	Stefan Porschen, Ewald Speckenmeyer	Worst Case Bounds for Some NP-Complete Modified Horn-SAT Problems.	SAT (Selected Papers	2004	DBLP DOI BibTeX RDF	(hidden) Horn formula, quadratic formula, minimal vertex cover, NP-completeness, satisfiability, fixed-parameter tractability
38	Tak-Ming Law	Fair Play Protocol.	Active Media Technology	2001	DBLP DOI BibTeX RDF	fairness, tractability, disputes
36	Gianluigi Greco, Francesco Scarcello	The power of tree projections: local consistency, greedy algorithms, and larger islands of tractability.	PODS	2010	DBLP DOI BibTeX RDF	structural decomposition methods, tree projections, local consistency
36	David A. Cohen, Martin James Green, Chris Houghton	Constraint Representations and Structural Tractability.	CP	2009	DBLP DOI BibTeX RDF
36	Miguel A. Gutiérrez-Naranjo, Mario J. Pérez-Jiménez, Agustin Riscos-Núñez, Francisco José Romero-Campero	Characterizing Tractability with Membrane Creation.	SYNASC	2005	DBLP DOI BibTeX RDF
36	Hubie Chen, Víctor Dalmau	(Smart) Look-Ahead Arc Consistency and the Pursuit of CSP Tractability.	CP	2004	DBLP DOI BibTeX RDF
34	Sergio Cabello, Panos Giannopoulos, Christian Knauer, Günter Rote	Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension.	SODA	2008	DBLP BibTeX RDF	clustering, complexity, lower bound, dimension, fixed-parameter tractability
34	Georg Gottlob, Phokion G. Kolaitis, Thomas Schwentick	Existential Second-Order Logic over Graphs: Charting the Tractability Frontier.	FOCS	2000	DBLP DOI BibTeX RDF	existential second-order logic, existential second-order formula, prefix class, first-order quantifiers, polynomial-time solvable problem, computational complexity, computational complexity, graph theory, graphs, directed graphs, NP-complete problems, formal logic, undirected graphs, descriptive complexity, tractability
34	Haim Kaplan, Ron Shamir, Robert Endre Tarjan	Tractability of parameterized completion problems on chordal and interval graphs: Minimum Fill-in and Physical Mapping	FOCS	1994	DBLP DOI BibTeX RDF	added edges, parameterized completion problems, minimum fill-in, NP-Hard graph completion problem, interval graphs, parameterized complexity, tractability, vertex coloring, physical mapping
31	Henryk Wozniakowski	Tractability and Strong Tractability of Linear Multivariate Problems.	J. Complex.	1994	DBLP DOI BibTeX RDF
30	Gösta Grahne, Adrian Onet	Data correspondence, exchange and repair.	ICDT	2010	DBLP DOI BibTeX RDF
30	Yasunori Ishihara, Takuji Morimoto, Shougo Shimizu, Kenji Hashimoto, Toru Fujiwara	A Tractable Subclass of DTDs for XPath Satisfiability with Sibling Axes.	DBPL	2009	DBLP DOI BibTeX RDF
30	Masayuki Murakami, Nakaji Honda	Performance of the IDS Method as a Soft Computing Tool.	IEEE Trans. Fuzzy Syst.	2008	DBLP DOI BibTeX RDF
30	Hans L. Bodlaender, Michael R. Fellows, Pinar Heggernes, Federico Mancini 0001, Charis Papadopoulos, Frances A. Rosamond	Clustering with Partial Information.	MFCS	2008	DBLP DOI BibTeX RDF
28	Nadja Betzler, Michael R. Fellows, Jiong Guo, Rolf Niedermeier, Frances A. Rosamond	How similarity helps to efficiently compute Kemeny rankings.	AAMAS (1)	2009	DBLP BibTeX RDF	structural parameterization, exact algorithm, NP-hard problem, fixed-parameter tractability, rank aggregation
28	Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier	Data reduction and exact algorithms for clique cover.	ACM J. Exp. Algorithmics	2008	DBLP DOI BibTeX RDF	Clique cover, data reduction, fixed-parameter tractability
28	Mathias Möhl, Sebastian Will, Rolf Backofen	Fixed Parameter Tractable Alignment of RNA Structures Including Arbitrary Pseudoknots.	CPM	2008	DBLP DOI BibTeX RDF	RNA alignment, fixed parameter tractability, pseudoknots
28	Georg Gottlob, Reinhard Pichler, Fang Wei 0001	Monadic datalog over finite structures with bounded treewidth.	PODS	2007	DBLP DOI BibTeX RDF	datalog, treewidth, fixed-parameter tractability, monadic second order logic, tree decomposition
28	Vincent Berry, François Nicolas	Improved Parameterized Complexity of the Maximum Agreement Subtree and Maximum Compatible Tree Problems.	IEEE ACM Trans. Comput. Biol. Bioinform.	2006	DBLP DOI BibTeX RDF	algorithms, pattern matching, trees, consensus, compatibility, fixed-parameter tractability, Phylogenetics
28	Georg Gottlob, Reinhard Pichler, Fang Wei 0001	Tractable database design through bounded treewidth.	PODS	2006	DBLP DOI BibTeX RDF	database design, normal forms, fixed-parameter tractability, tree decomposition, bounded treewidth
28	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
28	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
28	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
28	Georg Gottlob, Francesco Scarcello, Martha Sideri	Fixed-Parameter Complexity in AI and Nonmonotonic Reasoning.	LPNMR	1999	DBLP DOI BibTeX RDF	Complexity, Logic Programming, Constraint Satisfaction, Nonmonotonic Reasoning, Fixed-parameter Tractability, Stable Models, Prime Implicants, Circumscription
28	Byron Dom	MDL estimation for small sample sizes and its application to segmenting binary strings.	CVPR	1997	DBLP DOI BibTeX RDF	MDL estimation, binary strings segmentation, minimum description length estimation, sharper code-length formulas, relative tractability, binary strings, piecewise Bernoulli assumption, Bernoulli source, pattern recognition, computer vision, computer vision, small sample sizes
28	Brandon Bennett, Anthony G. Cohn 0001, Amar Isli	Combining Multiple Representations in a Spatial Reasoning System.	ICTAI	1997	DBLP DOI BibTeX RDF	spatial reasoning system, quantitative representations, numerical coordinate systems, high-level conceptual vocabulary, qualitative languages, computational tractability, first-order language, intuitionistic propositional logic, quantitative data structures, polygonal regions, qualitative relational language, high-level queries, spatial reasoning, multiple representations, topological relations, spatial information systems, qualitative representations
28	James M. Butler	Quantum modeling of distributed object computing.	Annual Simulation Symposium	1995	DBLP DOI BibTeX RDF	quantum modeling, computer engineering community, large scale design, large scale verification, LCN model, real-world network topologies, DCO model, system-independent method, complex object oriented computing structures, DCO software mapping, object system mapping model, OSM model, modeling, software engineering, design, message passing, tools, local area networks, digital simulation, object-oriented methods, client-server systems, dynamic models, large scale systems, random processes, tractability, multicomputer systems, distributed object computing, random variables, mission critical systems
28	Jean-Pierre Corriveau	A time-constrained architecture for cognition.	HICSS (3)	1995	DBLP DOI BibTeX RDF	time-constrained architecture, computational approaches, static strategy, diachronic nature, strong tractability, epistemological commitments, time-constrained model, massively parallel network, simple signals, object-oriented hierarchy, parallel architectures, knowledge based systems, software reliability, software reliability, memory, knowledge base, cognition, cognitive architectures, cognitive architecture, cognitive systems
28	Lotfi A. Zadeh	Soft Computing and Fuzzy Logic.	IEEE Softw.	1994	DBLP DOI BibTeX RDF	low solution cost, human mind, software engineering, software engineering, fuzzy logic, fuzzy logic, robustness, uncertainty, neural nets, inference mechanisms, soft computing, probabilistic reasoning, uncertainty handling, tractability, imprecision, neurocomputing, software methodologies
28	Thin-Fong Tsuei, Mary K. Vernon	A Multiprocessor Bus Design Model Validated by System Measurement.	IEEE Trans. Parallel Distributed Syst.	1992	DBLP DOI BibTeX RDF	commercial multiprocessor bus, bus design, asynchronous memorywrite operations, in-order delivery, processor read requests, memoryresponses, outstanding processor requests, two-level hierarchical model, mean value analysis techniques, measured system performance, parallel program workloads, memory access characteristics, analytic queueing models, model tractability, detailed simulation, system design tradeoffs, parallel programming, formal verification, Markov chain, Markov processes, queueing theory, multiprocessing systems, queueing networks, system buses, priority scheduling, performanceevaluation, system measurement
26	Binhai Zhu	Approximability and Fixed-Parameter Tractability for the Exemplar Genomic Distance Problems.	TAMC	2009	DBLP DOI BibTeX RDF
26	Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx	Minimizing Movement: Fixed-Parameter Tractability.	ESA	2009	DBLP DOI BibTeX RDF
26	Bruno Marnette	Generalized schema-mappings: from termination to tractability.	PODS	2009	DBLP DOI BibTeX RDF	weak acyclicity, data exchange, core, universal solution
26	Leo van Iersel, Judith Keijsper, Steven Kelk, Leen Stougie	Shorelines of Islands of Tractability: Algorithms for Parsimony and Minimum Perfect Phylogeny Haplotyping Problems.	IEEE ACM Trans. Comput. Biol. Bioinform.	2008	DBLP DOI BibTeX RDF	Biology and genetics, Combinatorial algorithms, Complexity hierarchies
26	Roman Barták, Ondrej Cepek	Nested Precedence Networks with Alternatives: Recognition, Tractability, and Models.	AIMSA	2008	DBLP DOI BibTeX RDF	temporal networks, complexity, alternatives, constraint models
26	Roded Sharan, Bjarni V. Halldórsson, Sorin Istrail	Islands of Tractability for Parsimony Haplotyping.	IEEE ACM Trans. Comput. Biol. Bioinform.	2006	DBLP DOI BibTeX RDF	graph algorithms, Biology and genetics, analysis of algorithms and problem complexity
26	Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, Anke Truß	Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments.	CIAC	2006	DBLP DOI BibTeX RDF
26	Chris Houghton, David A. Cohen, Martin James Green	The Effect of Constraint Representation on Structural Tractability.	CP	2006	DBLP DOI BibTeX RDF
26	Leo van Iersel, Judith Keijsper, Steven Kelk, Leen Stougie	Beaches of Islands of Tractability: Algorithms for Parsimony and Minimum Perfect Phylogeny Haplotyping Problems.	WABI	2006	DBLP DOI BibTeX RDF
26	Frank K. H. A. Dehne	FPT at Work: Using Fixed Parameter Tractability to Solve Larger Instances of Hard Problems.	IWPEC	2006	DBLP DOI BibTeX RDF
26	Jiong Guo, Rolf Niedermeier, Sebastian Wernicke 0001	Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual.	IWPEC	2006	DBLP DOI BibTeX RDF
26	Martin Scholz	On the Tractability of Rule Discovery from Distributed Data.	ICDM	2005	DBLP DOI BibTeX RDF
26	Marion G. Ceruti, Stuart Harvey Rubin	Infodynamics III: Information Integration and Tractability.	IRI	2005	DBLP DOI BibTeX RDF
26	Hubie Chen, Víctor Dalmau	From Pebble Games to Tractability: An Ambidextrous Consistency Algorithm for Quantified Constraint Satisfaction.	CSL	2005	DBLP DOI BibTeX RDF
26	Richard Gault, Peter Jeavons 0001	Implementing a Test for Tractability.	Constraints An Int. J.	2004	DBLP DOI BibTeX RDF	Polyanna, complexity, polymorphism, symmetry, constraint language
26	Jörg Flum, Martin Grohe, Mark Weyer	Bounded Fixed-Parameter Tractability and log2n Nondeterministic Bits.	ICALP	2004	DBLP DOI BibTeX RDF
26	Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Toby Walsh	The Tractability of Global Constraints.	CP	2004	DBLP DOI BibTeX RDF
26	Mark Weyer	Bounded Fixed-Parameter Tractability: The Case 2poly(k).	IWPEC	2004	DBLP DOI BibTeX RDF
20	Marek Karpinski, Andrzej Rucinski 0001, Edyta Szymanska	The Complexity of Perfect Matching Problems on Dense Hypergraphs.	ISAAC	2009	DBLP DOI BibTeX RDF
20	Andrea Calì, Georg Gottlob, Andreas Pieris	Tractable Query Answering over Conceptual Schemata.	ER	2009	DBLP DOI BibTeX RDF
20	Foto N. Afrati, Phokion G. Kolaitis	Repair checking in inconsistent databases: algorithms and complexity.	ICDT	2009	DBLP DOI BibTeX RDF	coNP-complete problem, equality-generating dependencies, repair checking, tuple-generating dependencies, weakly acyclic set, polynomial time, consistent query answering, inconsistent databases, database repairs
20	Sue Whitesides	Intractability in Graph Drawing and Geometry: FPT Approaches.	IWOCA	2009	DBLP DOI BibTeX RDF
20	Michael Jakl, Reinhard Pichler, Stefan Rümmele, Stefan Woltran	Fast Counting with Bounded Treewidth.	LPAR	2008	DBLP DOI BibTeX RDF
20	Francesco Scarcello, Georg Gottlob, Gianluigi Greco	Uniform Constraint Satisfaction Problems and Database Theory.	Complexity of Constraints	2008	DBLP DOI BibTeX RDF
20	Luca Trevisan	Average-case Complexity.	FOCS	2008	DBLP DOI BibTeX RDF
20	Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe	Copeland Voting Fully Resists Constructive Control.	AAIM	2008	DBLP DOI BibTeX RDF	Computational social choice theory, multiagent systems, preference aggregation
20	Vibhore Kumar, Brian F. Cooper, Greg Eisenhauer, Karsten Schwan	iManage: Policy-Driven Self-management for Enterprise-Scale Systems.	Middleware	2007	DBLP DOI BibTeX RDF	Bayesian Networks, Policies, Self-Management, Enterprise-Systems
20	Benny Kimelfeld, Yehoshua Sagiv	Incrementally Computing Ordered Answers of Acyclic Conjunctive Queries.	NGITS	2006	DBLP DOI BibTeX RDF
20	Patrick Bosc, Olivier Pivert	About projection-selection-join queries addressed to possibilistic relational databases.	IEEE Trans. Fuzzy Syst.	2005	DBLP DOI BibTeX RDF
20	Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien	Tractable Clones of Polynomials over Semigroups.	CP	2005	DBLP DOI BibTeX RDF
20	Andrei A. Krokhin, Benoît Larose	Maximum Constraint Satisfaction on Diamonds.	CP	2005	DBLP DOI BibTeX RDF
20	Phokion G. Kolaitis	Constraint Satisfaction, Complexity, and Logic.	SETN	2004	DBLP DOI BibTeX RDF
20	Wiebe van der Hoek, Michael J. Wooldridge	Cooperation, Knowledge, and Time: Alternating-time Temporal Epistemic Logic and its Applications.	Stud Logica	2003	DBLP DOI BibTeX RDF	Cooperation logic, model checking, game theory, epistemic logic
20	Michael J. Wooldridge	Time, Knowledge, and Cooperation: Alternating-Time Temporal Epistemic Logic and Its Applications.	KI	2002	DBLP DOI BibTeX RDF
20	Michael J. Wooldridge, Wiebe van der Hoek	Time, Knowledge, and Cooperation: Alternating-Time Temporal Epistemic Logic and Its Applications.	COORDINATION	2002	DBLP DOI BibTeX RDF
20	Víctor Dalmau, Phokion G. Kolaitis, Moshe Y. Vardi	Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics.	CP	2002	DBLP DOI BibTeX RDF
20	Richard Butterworth, Ann Blandford, David J. Duke	Demonstrating the Cognitive Plausibility of Interactive System Specifications.	Formal Aspects Comput.	2000	DBLP DOI BibTeX RDF	Programmable User Modelling (PUM), Cognitive plausibility, Electronic diary systems, Human-Computer Interaction (HCI), Interactive systems, Formal modelling
20	Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons 0001	Constraint Satisfaction Problems and Finite Algebras.	ICALP	2000	DBLP DOI BibTeX RDF
20	Thomas Eiter, Thomas Lukasiewicz	New Tractable Cases in Default Reasoning from Conditional Knowledge Bases.	JELIA	2000	DBLP DOI BibTeX RDF
20	Juraj Hromkovic	Stability of Approximation Algorithms for Hard Optimization Problems.	SOFSEM	1999	DBLP DOI BibTeX RDF
20	Michael R. Fellows, Michael T. Hallett, Chantal Korostensky, Ulrike Stege	Analogs and Duals of the MAST Problem for Sequences and Trees.	ESA	1998	DBLP DOI BibTeX RDF
20	Latha S. Colby, Leonid Libkin	Tractable Iteration Mechanisms for Bag Languages.	ICDT	1997	DBLP DOI BibTeX RDF
18	Dániel Marx	Tractable hypergraph properties for constraint satisfaction and conjunctive queries.	STOC	2010	DBLP DOI BibTeX RDF	submodular width, constraint satisfaction, conjunctive queries, fixed-parameter tractability
18	Dániel Marx	Completely Inapproximable Monotone and Antimonotone Parameterized Problems.	CCC	2010	DBLP DOI BibTeX RDF	parameterized comlexity, approximation, fixed-parameter tractability, inapproximability
18	Grzegorz W. Wasilkowski, Henryk Wozniakowski	Polynomial-Time Algorithms for Multivariate Linear Problems with Finite-Order Weights: Average Case Setting.	Found. Comput. Math.	2009	DBLP DOI BibTeX RDF	Multivariate linear problems, Finite-order weights, Small effective dimension, Average case setting, Polynomial-time algorithms, Tractability
18	Jianer Chen, Yang Liu 0002, Songjian Lu	An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem.	Algorithmica	2009	DBLP DOI BibTeX RDF	Multiway cut problem, Network flow, Fixed-parameter tractability, Minimum cut, Parameterized algorithm
18	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