New Approaches for Difference Constraint Systems

Abstract

In this report we summarize our contributions over the period 2006-2010. The principal objective of our work is the design, development and analysis of fundamentally new techniques for the problem of solving conjunctions of difference constraints. This problem is well-known to be equivalent to the problem of checking whether a directed graph (network) with positive and negative weights on its edges has a negative cost cycle (NCCD). The NCCD problem finds applications in a number of different design domains such as Program Verification, Real-Time Scheduling and Operations Research. We have looked at several variants of the NCCD problem, including the lightest negative cycle problem, the Horn constraint problem and the Unit Two Variable Per Inequality constraint problem. Each of the specialized constraint classes Our work has resulted in numerous publications in respected journals and conferences.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 2010
Accession Number
ADA563551

Entities

People

  • K. Subramani

Organizations

  • West Virginia University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Applied Mathematics
  • Artificial Intelligence
  • Artificial Intelligence Computing
  • Automata
  • Automata Theory
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Contracts
  • Detection
  • Mathematics
  • Operations Research
  • Random Walk
  • Scheduling (Production)

Fields of Study

  • Computer science

Readers

  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Graph Algorithms and Convex Optimization.
  • Systems Analysis and Design