Polynomial-delay enumeration algorithms in set systems

Abstract: We consider a set system

(V, m a t h c a l C s u b s e t e q 2^{V})

on a finite set

V

of elements, where we call a set

C i n m a t h c a l C

a component. We assume that two oracles

m a t h r m L_{1}

and

m a t h r m L_{2}

are available, where given two subsets

X, Y s u b s e t e q V

,

m a t h r m L_{1}

returns a maximal component

C i n m a t h c a l C

with

X s u b s e t e q C s u b s e t e q Y

; and given a set

Y s u b s e t e q V

,

m a t h r m L_{2}

returns all maximal components

C i n m a t h c a l C

with

C s u b s e t e q Y

. Given a set

I

of attributes and a function

s i g m a : V o 2^{I}

in a transitive system, a component

C i n m a t h c a l C

is called a solution if the set of common attributes in

C

is inclusively maximal; i.e.,

for any component

X i n m a t h c a l C

with

C s u b s e t n e q X

. We prove that there exists an algorithm of enumerating all solutions (or all components) in delay bounded by a polynomial with respect to the input size and the running times of the oracles.

Recommendations

Cites work

This page was built for publication: Polynomial-delay enumeration algorithms in set systems

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