Search results for "tractable"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
63	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
57	Georg Gottlob, Zoltán Miklós 0001, 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
57	Georg Gottlob, Zoltán Miklós 0001, Thomas Schwentick	Generalized hypertree decompositions: np-hardness and tractable variants.	PODS	2007	DBLP DOI BibTeX RDF	hypertree decomposition, tree projection problem, NP-complete, hypergraph, conjunctive query, tractable, acyclic
57	David A. Cohen, Peter Jeavons 0001, Richard Gault	New Tractable Classes From Old.	Constraints An Int. J.	2003	DBLP DOI BibTeX RDF	tractable classes, disjunctive constraints, complexity, constraint satisfaction problems
53	Manolis Koubarakis, Spiros Skiadopoulos	Tractable Query Answering in Indefinite Constraint Databases: Basic Results and Applications to Querying Spatiotemporal Information.	Spatio-Temporal Database Management	1999	DBLP DOI BibTeX RDF
50	Lih-Chung Wang, Yuh-Hua Hu, Feipei Lai, Chun-yen Chou, Bo-Yin Yang	Tractable Rational Map Signature.	Public Key Cryptography	2005	DBLP DOI BibTeX RDF	tractable rational maps, digital signature, finite field, public key, multivariate
50	Antoine Joux, Sébastien Kunz-Jacques, Frédéric Muller, Pierre-Michel Ricordel	Cryptanalysis of the Tractable Rational Map Cryptosystem.	Public Key Cryptography	2005	DBLP DOI BibTeX RDF	Tractable Rational Map Cryptosystem, XL, Gröbner Bases, Isomorphism of Polynomials, Public Key Cryptography, Polynomial Systems
46	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
43	Yorick Wilks, Dan Fass, Cheng-ming Guo, James E. McDonald, Tony Plate, Brian M. Slator	Providing machine tractable dictionary tools.	Mach. Transl.	1990	DBLP DOI BibTeX RDF	computational lexicography, machine tractable dictionaries, pathfinder networkds, preference semantics, semantic primitives, word-sense disambiguation
37	Michael R. Fellows, Christian Knauer, Naomi Nishimura, Prabhakar Ragde, Frances A. Rosamond, Ulrike Stege, Dimitrios M. Thilikos, Sue Whitesides	Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems.	Algorithmica	2008	DBLP DOI BibTeX RDF	Graph matching, Fixed parameter tractable, Parameterized complexity, Color coding, Set packing
37	Thomas J. Weigert, Jeffrey J. P. Tsai	A Computationally Tractable Nonmonotonic Logic.	IEEE Trans. Knowl. Data Eng.	1994	DBLP DOI BibTeX RDF	computationally tractable nonmonotonic logic, nonmonotonic reasoning procedures, proof theoretically, semantic characteristics, Herbrand subset, knowledge representation, logic programming, logic programming, reasoning, nonmonotonic reasoning, incomplete information, formal logic, first-order predicate logic
37	Noga Alon, Shai Gutner	Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs.	Algorithmica	2009	DBLP DOI BibTeX RDF	H-minor-free graphs, Degenerated graphs, Dominating set problem, Finding an induced cycle, Fixed-parameter tractable algorithms
37	Petr Hlinený, Sang-il Oum	Finding Branch-Decompositions and Rank-Decompositions.	ESA	2007	DBLP DOI BibTeX RDF	Rank-width, fixed parameter tractable algorithm, graph, matroid, clique-width, branch-width
37	Noga Alon, Shai Gutner	Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs.	COCOON	2007	DBLP DOI BibTeX RDF	H-minor-free graphs, degenerated graphs, dominating set problem, finding an induced cycle, fixed-parameter tractable algorithms
33	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
33	Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Elena Losievskaja, Frances A. Rosamond, Saket Saurabh 0001	Distortion Is Fixed Parameter Tractable.	ICALP (1)	2009	DBLP DOI BibTeX RDF
33	Andrea Calì, Georg Gottlob, Thomas Lukasiewicz	A general datalog-based framework for tractable query answering over ontologies.	PODS	2009	DBLP DOI BibTeX RDF	ontologies, semantic web, complexity, constraints, dependencies, datalog, conjunctive queries, query evaluation, tractability, chase
33	Marco Falda	A Method for Characterizing Tractable Subsets of Qualitative Fuzzy Temporal Algebrae.	WILF	2005	DBLP DOI BibTeX RDF	Representation of Vague and Imprecise Knowledge, Fuzzy Sets, Possibility Theory
33	David A. Cohen, Peter Jeavons 0001, Richard Gault	New Tractable Classes from Old.	CP	2000	DBLP DOI BibTeX RDF
33	Ninghui Li, Benjamin N. Grosof, Joan Feigenbaum	A Practically Implementable and Tractable Delegation Logic.	S&P	2000	DBLP DOI BibTeX RDF	access control, knowledge representation, logic programs, Authorization, security policies, trust management, delegation
33	Hannes Moser, Venkatesh Raman 0001, Somnath Sikdar	The Parameterized Complexity of the Unique Coverage Problem.	ISAAC	2007	DBLP DOI BibTeX RDF
33	Ana-Maria Popescu, Oren Etzioni, Henry A. Kautz	Towards a theory of natural language interfaces to databases.	IUI	2003	DBLP DOI BibTeX RDF	reliability, database, natural language interface
30	Joachim Biskup, David W. Embley	Mediated Information Gain.	IDEAS	2000	DBLP DOI BibTeX RDF	mediated information gain, human burden, algorithmically tractable subtasks, quality level, mediation task, formal information state, returned answer, internal consistency maintenance, relevant source parts, searching, information systems, implementation, embeddings, querying, completeness, rules, correctness, user interactions, updating, sensor fusion, high-level architecture, iteration, schema, precision, revisions, heterogeneous data sources, instance, query specifications
30	Thierry Vidal, Hélène Fargier	Contingent Durations in Temporal CSPs: From Consistency to Controllabilities.	TIME	1997	DBLP DOI BibTeX RDF	temporal CSPs, Temporal Constraint Networks, classical network consistency property, Strong, Weak, reasoning issues, tractable subclasses, complexity, controllability, controllability, Dynamic
27	Justyna Petke, Peter Jeavons 0001	The Order Encoding: From Tractable CSP to Tractable SAT.	SAT	2011	DBLP DOI BibTeX RDF
27	David A. Cohen	Tractable Decision for a Constraint Language Implies Tractable Search.	Constraints An Int. J.	2004	DBLP DOI BibTeX RDF	complexity, language, tractability
27	Peter Jonsson, Christer Bäckström	Tractable Plan Existence Does Not Imply Tractable Plan Generation.	Ann. Math. Artif. Intell.	1998	DBLP DOI BibTeX RDF
27	Andrea Calì, Georg Gottlob, Andreas Pieris	Tractable Query Answering over Conceptual Schemata.	ER	2009	DBLP DOI BibTeX RDF
27	Frauke Oldewurtel, Colin N. Jones, Manfred Morari	A tractable approximation of chance constrained stochastic MPC based on affine disturbance feedback.	CDC	2008	DBLP DOI BibTeX RDF
27	András Z. Salamon, Peter G. Jeavons	Perfect Constraints Are Tractable.	CP	2008	DBLP DOI BibTeX RDF
27	Bruno Escoffier, Jérôme Monnot, Olivier Spanjaard	Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality.	SOFSEM	2008	DBLP DOI BibTeX RDF	Bipartite perfect matching, Shortest path, Spanning tree, Robust optimization, Interval data
27	Thomas Lukasiewicz	Tractable Probabilistic Description Logic Programs.	SUM	2007	DBLP DOI BibTeX RDF
27	Marina Meila, Tommi S. Jaakkola	Tractable Bayesian learning of tree belief networks.	Stat. Comput.	2006	DBLP DOI BibTeX RDF	Tree belief network, Decomposable prior, Matrix tree theorem, Spanning tree, Graphical model, Bayesian
27	Berilhes Borges Garcia	New tractable classes for default reasoning from conditional knowledge bases.	Ann. Math. Artif. Intell.	2005	DBLP DOI BibTeX RDF	AMS subject classification 68T27
27	Jure Leskovec, Deepayan Chakrabarti, Jon M. Kleinberg, Christos Faloutsos	Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication.	PKDD	2005	DBLP DOI BibTeX RDF
27	Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien	Tractable Clones of Polynomials over Semigroups.	CP	2005	DBLP DOI BibTeX RDF
27	Alfonso Bosch, Francisco Guil, Roque Marín	A Tractable Subclass of Fuzzy Constraint Networks.	EUROCAST	2005	DBLP DOI BibTeX RDF
27	Jens Gramm, Till Nierhoff, Till Tantau	Perfect Path Phylogeny Haplotyping with Missing Data Is Fixed-Parameter Tractable.	IWPEC	2004	DBLP DOI BibTeX RDF
27	Martin Grohe, Thomas Schwentick, Luc Segoufin	When is the evaluation of conjunctive queries tractable?	STOC	2001	DBLP DOI BibTeX RDF
27	Thomas Eiter, Thomas Lukasiewicz	New Tractable Cases in Default Reasoning from Conditional Knowledge Bases.	JELIA	2000	DBLP DOI BibTeX RDF
27	Mathias Broxvall, Peter Jonsson, Jochen Renz	Refinements and Independence: A Simple Method for Identifying Tractable Disjunctive Constraints.	CP	2000	DBLP DOI BibTeX RDF
27	Georg Gottlob, Nicola Leone, Francesco Scarcello	On Tractable Queries and Constraints.	DEXA	1999	DBLP DOI BibTeX RDF
27	Bernhard Nebel, Hans-Jürgen Bürckert	Reasoning about Temporal Relations: A Maximal Tractable Subclass of Allen's Interval Algebra.	J. ACM	1995	DBLP DOI BibTeX RDF	constraint satisfaction, temporal reasoning, qualitative reasoning, interval algebra
27	Shing-Chi Cheung, Jeff Kramer	Tractable Dataflow Analysis for Distributed Systems.	IEEE Trans. Software Eng.	1994	DBLP DOI BibTeX RDF	action dependency, history sets, pump control system, arbitrary loops, nondeterministic structures, synchronous communicating systems, distributed systems, software engineering, static analysis, distributed processing, program verification, reachability analysis, labeled transition systems, dataflow analysis, software development tools, distributed software engineering, worst-case complexity
26	Andrei A. Bulatov	A dichotomy theorem for constraint satisfaction problems on a 3-element set.	J. ACM	2006	DBLP DOI BibTeX RDF	dichotomy theorem, homomorphism problem, complexity, Constraint satisfaction problem
26	David A. Cohen, Martin James Green	Typed Guarded Decompositions for Constraint Satisfaction.	CP	2006	DBLP DOI BibTeX RDF
26	Jörg Flum, Martin Grohe, Mark Weyer	Bounded Fixed-Parameter Tractability and log2n Nondeterministic Bits.	ICALP	2004	DBLP DOI BibTeX RDF
26	Venkatesh Raman 0001, Saket Saurabh 0001	Parameterized Complexity of Directed Feedback Set Problems in Tournaments.	WADS	2003	DBLP DOI BibTeX RDF
26	Andrei A. Bulatov	A Dichotomy Theorem for Constraints on a Three-Element Set.	FOCS	2002	DBLP DOI BibTeX RDF
23	Shai Gutner	Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor.	IWPEC	2009	DBLP DOI BibTeX RDF	H-minor-free graphs, degenerated graphs, dominating set problem, fixed-parameter tractable algorithms, problem kernel
20	Philippe Rolet, Michèle Sebag, Olivier Teytaud	Boosting Active Learning to Optimality: A Tractable Monte-Carlo, Billiard-Based Algorithm.	ECML/PKDD (2)	2009	DBLP DOI BibTeX RDF
20	Refael Hassin, R. Ravi 0001, F. Sibel Salman	Tractable Cases of Facility Location on a Network with a Linear Reliability Order of Links.	ESA	2009	DBLP DOI BibTeX RDF
20	Georg Gottlob, Gianluigi Greco, Francesco Scarcello	Tractable Optimization Problems through Hypergraph-Based Structural Restrictions.	ICALP (2)	2009	DBLP DOI BibTeX RDF
20	Kun-Jung Hsu, Jonathan Shi	A tractable time-cost tradeoff algorithm for project activity management.	SpringSim	2009	DBLP DOI BibTeX RDF	time-cost trade-off, sensitivity analysis, mathematical programming, critical path, parametric programming
20	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
20	Ryan Prescott Adams, Iain Murray 0001, David J. C. MacKay	Tractable nonparametric Bayesian inference in Poisson processes with Gaussian process intensities.	ICML	2009	DBLP DOI BibTeX RDF
20	András Faragó	A General Tractable Density Concept for Graphs.	Math. Comput. Sci.	2008	DBLP DOI BibTeX RDF	graph density, densest subgraph, Graph algorithm
20	Venkat Chandrasekaran, Jason K. Johnson, Alan S. Willsky	Estimation in Gaussian Graphical Models Using Tractable Subgraphs: A Walk-Sum Analysis.	IEEE Trans. Signal Process.	2008	DBLP DOI BibTeX RDF
20	Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler	ELP: Tractable Rules for OWL 2.	ISWC	2008	DBLP DOI BibTeX RDF
20	Vineet Kahlon	Parameterization as Abstraction: A Tractable Approach to the Dataflow Analysis of Concurrent Programs.	LICS	2008	DBLP DOI BibTeX RDF	Model Checking, Concurrent Programs, Dataflow Analysis, Parameterized Systems, Pushdown Systems
20	Igor Razgon, Barry O'Sullivan	Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract).	ICALP (1)	2008	DBLP DOI BibTeX RDF
20	Michael Botros Shenouda, Timothy N. Davidson	Tractable approaches to fair QoS broadcast precoding under channel uncertainty.	ICASSP	2008	DBLP DOI BibTeX RDF
20	Steven Y. Ko, Imranul Hoque, Indranil Gupta	Using Tractable and Realistic Churn Models to Analyze Quiescence Behavior of Distributed Protocols.	SRDS	2008	DBLP DOI BibTeX RDF
20	Magnus Bordewich, Charles Semple	Computing the Hybridization Number of Two Phylogenetic Trees Is Fixed-Parameter Tractable.	IEEE ACM Trans. Comput. Biol. Bioinform.	2007	DBLP DOI BibTeX RDF	Rooted phylogenetic tree, reticulate evolution, agreement forest, subtree prune and regraft, hybridization network
20	Georg Gottlob, Gianluigi Greco	Combinatorial auctions with tractable winner determination.	SIGecom Exch.	2007	DBLP DOI BibTeX RDF
20	Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler	Conjunctive Queries for a Tractable Fragment of OWL 1.1.	ISWC/ASWC	2007	DBLP DOI BibTeX RDF
20	Oliver C. Schrempf, David Albrecht, Uwe D. Hanebeck	Tractable probabilistic models for intention recognition based on expert knowledge.	IROS	2007	DBLP DOI BibTeX RDF
20	Yang Xiang 0004	Tractable Optimal Multiagent Collaborative Design.	IAT	2007	DBLP DOI BibTeX RDF
20	Martin Grohe	The Structure of Tractable Constraint Satisfaction Problems.	MFCS	2006	DBLP DOI BibTeX RDF
20	Dániel Marx	Chordal Deletion Is Fixed-Parameter Tractable.	WG	2006	DBLP DOI BibTeX RDF
20	Peter Damaschke	Fixed-Parameter Tractable Generalizations of Cluster Editing.	CIAC	2006	DBLP DOI BibTeX RDF
20	Nicola Fanizzi, Luigi Iannone, Nicola Di Mauro, Floriana Esposito	Tractable Feature Generation Through Description Logics with Value and Number Restrictions.	IEA/AIE	2006	DBLP DOI BibTeX RDF
20	K. Subramani 0001	Tractable Fragments of Presburger Arithmetic.	Theory Comput. Syst.	2005	DBLP DOI BibTeX RDF
20	Hubie Chen	Periodic Constraint Satisfaction Problems: Tractable Subclasses.	Constraints An Int. J.	2005	DBLP DOI BibTeX RDF	periodic problems, polynomial-time algorithms
20	Víctor Dalmau	Generalized Majority-Minority Operations are Tractable.	LICS	2005	DBLP DOI BibTeX RDF
20	Kian Ming Adam Chai	Expectation of f-measures: tractable exact computation and some empirical observations of its properties.	SIGIR	2005	DBLP DOI BibTeX RDF	optimisation, thresholding, F-measures
20	Patrick Healy, Karol Lynch	Fixed-Parameter Tractable Algorithms for Testing Upward Planarity.	SOFSEM	2005	DBLP DOI BibTeX RDF
20	Mohamed S. Hassan 0001, Marwan Krunz, Ibrahim Matta	Markov-based channel characterization for tractable performance analysis in wireless packet networks.	IEEE Trans. Wirel. Commun.	2004	DBLP DOI BibTeX RDF
20	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
20	Hubie Chen, Víctor Dalmau	Looking Algebraically at Tractable Quantified Boolean Formulas.	SAT (Selected Papers	2004	DBLP DOI BibTeX RDF
20	Cliff B. Jones	The Early Search for Tractable Ways of Reasoning about Programs.	IEEE Ann. Hist. Comput.	2003	DBLP DOI BibTeX RDF
20	Andrei A. Bulatov	Tractable conservative Constraint Satisfaction Problems.	LICS	2003	DBLP DOI BibTeX RDF
20	Ugo Dal Lago, Angelo Montanari, Gabriele Puppis	Towards Compact and Tractable Automaten-Based Representations of Time Granularities.	ICTCS	2003	DBLP DOI BibTeX RDF
20	Stefan Szeider	Minimal Unsatisfiable Formulas with Bounded Clause-Variable Difference are Fixed-Parameter Tractable.	COCOON	2003	DBLP DOI BibTeX RDF
20	Per Carlsson, Arne Andersson, Fredrik Ygge	A Tractable Mechanism for Time Dependent Markets.	CEC	2003	DBLP DOI BibTeX RDF
20	Venkatesh Raman 0001, Saket Saurabh 0001, C. R. Subramanian 0001	Faster Fixed Parameter Tractable Algorithms for Undirected Feedback Vertex Set.	ISAAC	2002	DBLP DOI BibTeX RDF
20	Bharat Adsul, Milind A. Sohoni	Complete and Tractable Local Linear Time Temporal Logics over Traces.	ICALP	2002	DBLP DOI BibTeX RDF	Concurrency, Temporal Logics, Limits, Mazurkiewicz Traces
20	Vida Dujmovic, Sue Whitesides	An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization.	GD	2002	DBLP DOI BibTeX RDF
20	John A. Ellis, Hongbing Fan, Michael R. Fellows	The Dominating Set Problem Is Fixed Parameter Tractable for Graphs of Bounded Genus.	SWAT	2002	DBLP DOI BibTeX RDF	graph, dominating set, fixed parameter algorithm, genus
20	Daniel P. Miranker, Malcolm C. Taylor, Anand Padmanaban	A Tractable Query Cache by Approximation.	SARA	2002	DBLP DOI BibTeX RDF
20	Wiebe van der Hoek, Michael J. Wooldridge	Tractable multiagent planning for epistemic goals.	AAMAS	2002	DBLP DOI BibTeX RDF	epistemic & temporal logic, model checking, planning
20	Jens Gramm, Rolf Niedermeier	Minimum Quartet Inconsistency Is Fixed Parameter Tractable.	CPM	2001	DBLP DOI BibTeX RDF
20	Edgar Altamirano, Gonzalo Escalada-Imaz	Finding Tractable Formulas in NNF.	Computational Logic	2000	DBLP DOI BibTeX RDF
20	Franz Baader, Ralf Molitor, Stephan Tobies	Tractable and Decidable Fragments of Conceptual Graphs.	ICCS	1999	DBLP DOI BibTeX RDF
20	Ulrike Stege	Gene Trees and Species Trees: The Gene-Duplication Problem in Fixed-Parameter Tractable.	WADS	1999	DBLP DOI BibTeX RDF
20	Latha S. Colby, Leonid Libkin	Tractable Iteration Mechanisms for Bag Languages.	ICDT	1997	DBLP DOI BibTeX RDF
20	Marko Samer, Stefan Szeider	Backdoor Sets of Quantified Boolean Formulas.	J. Autom. Reason.	2009	DBLP DOI BibTeX RDF	Backdoor sets, Variable dependencies, Parameterized complexity, Quantified Boolean formulas
20	Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh 0001	Clique-width: on the price of generality.	SODA	2009	DBLP DOI BibTeX RDF
20	Dan Olteanu, Jiewen Huang, Christoph Koch 0001	SPROUT: Lazy vs. Eager Query Plans for Tuple-Independent Probabilistic Databases.	ICDE	2009	DBLP DOI BibTeX RDF
20	Miki Hermann, Florian Richoux	On the Computational Complexity of Monotone Constraint Satisfaction Problems.	WALCOM	2009	DBLP DOI BibTeX RDF