Satisfiability problems on intervals and unit intervals

DOI10.1016/S0304-3975(96)00208-3MaRDI QIDQ1392209zbMATH OpenOpenAlexFDO

Authors Itsik Pe'er, Ron Shamir

Publication date 23 July 1998

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(96)00208-3

zbMATH Keywords

order constraints

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Recommendations

• Interval graphs with side (and size) constraints
• Constraint Satisfaction Problems on Intervals and Lengths
• Realizing Interval Graphs with Size and Distance Constraints
• On satisfiability problems with a linear structure
• Complexity and algorithms for reasoning about time

Cites work

• A Characterization of Comparability Graphs and of Interval Graphs
• A linear time and space algorithm to recognize interval orders
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Complexity and algorithms for reasoning about time
• Construction of ternary H_v-groups and ternary P-hyperoperations.
• scientific article; zbMATH DE number 3877239 (Why is no real title available?)
• scientific article; zbMATH DE number 3908482 (Why is no real title available?)
• scientific article; zbMATH DE number 52880 (Why is no real title available?)
• scientific article; zbMATH DE number 3566474 (Why is no real title available?)
• scientific article; zbMATH DE number 512914 (Why is no real title available?)
• scientific article; zbMATH DE number 3215831 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• Incidence matrices and interval graphs
• Incidence matrices, interval graphs and seriation in archeology
• Interval graphs and related topics
• Interval graphs with side (and size) constraints
• Intransitive indifference with unequal indifference intervals
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Maintaining knowledge about temporal intervals
• Mapping the genome
• Network flows. Theory, algorithms, and applications.
• New scaling algorithms for the assignment and minimum mean cycle problems
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Scheduling Interval-Ordered Tasks
• Temporally distributed symptoms in technical diagnosis
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The complexity of satisfiability problems

Cited in

(10)

• Numerical representation of PQI interval orders
• Proof of the interval satisfiability conjecture
• Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
• On satisfiability problems with a linear structure
• Constraint Satisfaction Problems on Intervals and Lengths
• Interval graphs with side (and size) constraints
• Solving infinite-domain CSPs using the patchwork property
• Width notions for ordering-related problems
• Algorithms and complexity of difference logic
• Representability of binary relations through fuzzy numbers

This page was built for publication: Satisfiability problems on intervals and unit intervals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1392209)