TY - JOUR

T1 - A review of tree convex sets test

AU - Sheng Bao, Forrest

AU - Zhang, Yuanlin

N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.

PY - 2012/8

Y1 - 2012/8

N2 - 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.

AB - 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.

KW - Combinatorial Auction Problems

KW - Constraint satisfaction problems

KW - consecutive ones property

KW - row convex constraints

KW - tree convex sets

UR - http://www.scopus.com/inward/record.url?scp=84864774521&partnerID=8YFLogxK

U2 - 10.1111/j.1467-8640.2012.00418.x

DO - 10.1111/j.1467-8640.2012.00418.x

M3 - Article

AN - SCOPUS:84864774521

VL - 28

SP - 358

EP - 372

JO - Computational Intelligence

JF - Computational Intelligence

SN - 0824-7935

IS - 3

ER -