Arrow Research search

Author name cluster

Trung Van Pham

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
1 author row

Possible papers

2

FLAP Journal 2018 Journal Article

A Complexity Dichotomy for Poset Constraint Satisfaction.

  • Michael Kompatscher
  • Trung Van Pham

In this paper we determine the complexity of a broad class of problems that extend the temporal constraint satisfaction problems classified by Bodirsky and Kára. To be more precise, we study problems Poset-SAT(Φ) where Φ is a given set of quantifier-free ≤-formulas. An instance of Poset-SAT(Φ) then consists of finitely many variables and constraints on them expressible in Φ; the question is then whether this input can be satisfied in some partial order or not. We show that every such problem is either NP-complete or in P, depending on the constraint language Φ. All Poset-SAT problems can be formalized as constraint satisfaction problems of reducts of the random partial order. We use model-theoretic concepts and techniques from universal algebra to study these reducts. In the course of this analysis we establish a dichotomy that we believe is of independent interest in universal algebra and model theory.

PDF Details

TCS Journal 2014 Journal Article

Fixed-point forms of the parallel symmetric sandpile model

  • Enrico Formenti
  • Trung Van Pham
  • Thi Ha Duong Phan
  • Thi Thu Huong Tran

This paper presents a generalization of the sandpile model, called the parallel symmetric sandpile model, which inherits the rule of the symmetric sandpile model and implements them in parallel. We prove that although the parallel model produces fewer fixed points than the sequential model, the forms of fixed points of the two models are the same. Moreover, our proof is a constructive one, which gives a nearly shortest way to reach a given fixed point form.

Details DOI
v2026.09.13