Complexity and algorithms for reasoning about time

DOI10.1145/174147.169675zbMath0795.68095OpenAlexW1972734518WikidataQ56267430 ScholiaQ56267430MaRDI QIDQ4285633

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

zbMATH Keywords

complexityNP-completesatisfiabilitytemporal reasoninginterval graphsinterval orderssandwich problemDNA mappinginterval algebras

Mathematics Subject Classification ID

Related Items (47)

The graph sandwich problem for 1-join composition is NP-complete ⋮ Solving multi-granularity temporal constraint networks ⋮ On neighbourhood singleton-style consistencies for qualitative spatial and temporal reasoning ⋮ A general method for forbidden induced subgraph sandwich problem NP-completeness ⋮ Sandwich and probe problems for excluding paths ⋮ Can transitive orientation make sandwich problems easier? ⋮ On point-based temporal disjointness ⋮ Modelling and solving temporal reasoning as propositional satisfiability ⋮ Simultaneous representation of interval and interval-containment orders ⋮ Spatial reasoning with rectangular cardinal relations. The convex tractable subalgebra ⋮ Succinct encodings for families of interval graphs ⋮ Extending partial representations of interval graphs ⋮ Proof of the interval satisfiability conjecture ⋮ Satisfiability problems on intervals and unit intervals ⋮ The interval order polytope of a digraph ⋮ Interval graphs with side (and size) constraints ⋮ Twenty-one large tractable subclasses of Allen's algebra ⋮ Reasoning about causality between distributed nonatomic events ⋮ Reasoning about visibility ⋮ Algorithms and complexity of sandwich problems in graphs (extended abstract) ⋮ Biorders with frontier ⋮ Efficient Computation of Minimal Point Algebra Constraints by Metagraph Closure ⋮ Modeling recreational systems using optimization techniques and information technologies ⋮ Incremental qualitative temporal reasoning: Algorithms for the point algebra and the ORD-Horn class ⋮ Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms ⋮ The complexity of querying indefinite data about linearly ordered domains ⋮ Unique Perfect Phylogeny Is NP-Hard ⋮ Solving hard qualitative temporal reasoning problems: Evaluating the efficiency of using the ORD-Horn class ⋮ Planning temporal events using point-interval logic ⋮ Guest editors' preface to special issue on interval temporal logics ⋮ Shiftable intervals ⋮ The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem ⋮ Computing the minimal relations in point-based qualitative temporal reasoning through metagraph closure ⋮ Numerical representation of \(PQI\) interval orders ⋮ Complexity classification of some edge modification problems ⋮ The sandwich problem for decompositions and almost monotone properties ⋮ Branching interval algebra: an almost complete picture ⋮ A unifying approach to temporal constraint reasoning ⋮ A complete classification of tractability in Allen's algebra relative to subsets of basic relations ⋮ On the proper intervalization of colored caterpillar trees ⋮ On coarser interval temporal logics ⋮ Collective singleton-based consistency for qualitative constraint networks: theory and practice ⋮ REASONING WITH TOPOLOGICAL AND DIRECTIONAL SPATIAL INFORMATION ⋮ Matrix sandwich problems ⋮ A comparison of point-based approaches to qualitative temporal reasoning ⋮ Point algebras for temporal reasoning: Algorithms and complexity ⋮ Complexity classification in qualitative temporal constraint reasoning

This page was built for publication: Complexity and algorithms for reasoning about time