Complexity and algorithms for reasoning about time
From MaRDI portal
Publication:4285633
DOI10.1145/174147.169675zbMATH Open0795.68095OpenAlexW1972734518WikidataQ56267430 ScholiaQ56267430MaRDI QIDQ4285633FDOQ4285633
Authors: Ron Shamir, Martin Charles Golumbic 
Publication date: 11 September 1994
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/174147.169675
Recommendations
complexityinterval graphsNP-completesatisfiabilitytemporal reasoninginterval orderssandwich problemDNA mappinginterval algebras
Protein sequences, DNA sequences (92D20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cited In (57)
- ON THE HARDNESS OF RECOGNIZING BUNDLES IN TIME TABLE GRAPHS
- Complexity classification transfer for CSPs via algebraic products
- On neighbourhood singleton-style consistencies for qualitative spatial and temporal reasoning
- Can transitive orientation make sandwich problems easier?
- Title not available (Why is that?)
- Satisfiability problems on intervals and unit intervals
- Reasoning about partially ordered events
- Reasoning about causality between distributed nonatomic events
- The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem
- Algorithms for Extracting Timeliness Graphs
- Computing the minimal relations in point-based qualitative temporal reasoning through metagraph closure
- Modelling and solving temporal reasoning as propositional satisfiability
- Solving hard qualitative temporal reasoning problems: Evaluating the efficiency of using the ORD-Horn class
- Algorithms and complexity of sandwich problems in graphs (extended abstract)
- Reasoning about visibility
- Extending partial representations of interval graphs
- Matrix sandwich problems
- The complexity of querying indefinite data about linearly ordered domains
- The interval order polytope of a digraph
- Simultaneous representation of interval and interval-containment orders
- Sandwich and probe problems for excluding paths
- Reasoning with topological and directional spatial information
- A general method for forbidden induced subgraph sandwich problem NP-completeness
- The graph sandwich problem for 1-join composition is NP-complete
- Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
- A complete classification of tractability in Allen's algebra relative to subsets of basic relations
- Efficient algorithms for the temporal precedence problem
- Twenty-one large tractable subclasses of Allen's algebra
- Solving multi-granularity temporal constraint networks
- A unifying approach to temporal constraint reasoning
- On coarser interval temporal logics
- A comparison of point-based approaches to qualitative temporal reasoning
- Collective singleton-based consistency for qualitative constraint networks: theory and practice
- Numerical representation of \(PQI\) interval orders
- Guest editors' preface to special issue on interval temporal logics
- Complexity classification of some edge modification problems
- Trends in Temporal Reasoning: Constraints, Graphs and Posets
- Unique perfect phylogeny is NP-hard
- Succinct encodings for families of interval graphs
- Proof of the interval satisfiability conjecture
- Incremental qualitative temporal reasoning: Algorithms for the point algebra and the ORD-Horn class
- Modeling recreational systems using optimization techniques and information technologies
- Branching interval algebra: an almost complete picture
- Interval graphs with side (and size) constraints
- The complexity of reasoning about knowledge and time. I: Lower bounds
- The sandwich problem for decompositions and almost monotone properties
- Biorders with frontier
- Spatial reasoning with rectangular cardinal relations. The convex tractable subalgebra
- On point-based temporal disjointness
- Shiftable intervals
- Planning temporal events using point-interval logic
- On the proper intervalization of colored caterpillar trees
- Efficient Computation of Minimal Point Algebra Constraints by Metagraph Closure
- Point algebras for temporal reasoning: Algorithms and complexity
- Timed Sets, Functional Complexity, and Computability
- Title not available (Why is that?)
- Complexity classification in qualitative temporal constraint reasoning
This page was built for publication: Complexity and algorithms for reasoning about time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4285633)
