A review of tree convex sets test

Forrest Sheng Bao, Yuanlin Zhang

Research output: Contribution to journalArticle

12 Scopus citations

Abstract

A collection of sets may have some interesting properties which help identify efficient algorithms for constraint satisfaction problems and combinatorial auction problems. One of the properties is tree convexity. A collection S of sets is tree convex if we can find a tree T whose nodes are the union of the sets of S and each set of S is the nodes of a subtree of T. This concept extends that of row convex sets each of which is an interval over a total ordering of the elements of the union of these sets. An interesting problem is to find efficient algorithms to test whether a collection of sets is tree convex. It is not known before if there exists a linear time algorithm for this test. In this paper, we review the materials that are the key to a linear algorithm: hypergraphs, a characterization of tree convex sets and the acyclic hypergraph test algorithm. Some typos in the original paper of the acyclicity test are corrected here. Some experiments show that the linear algorithm is significantly faster than a well-known existing algorithm.

Original languageEnglish
Pages (from-to)358-372
Number of pages15
JournalComputational Intelligence
Volume28
Issue number3
DOIs
StatePublished - Aug 2012

Keywords

  • Combinatorial Auction Problems
  • Constraint satisfaction problems
  • consecutive ones property
  • row convex constraints
  • tree convex sets

Fingerprint Dive into the research topics of 'A review of tree convex sets test'. Together they form a unique fingerprint.

Cite this