Presentation | 1994/10/21 Generating and Approximating Non-Dominated Coteries J.C. Bioch, Toshihide Ibaraki, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | A coterie,which is used to realize mutual exclusion in a distributed system,is a family C of incomparable subsets such that every pair of subsets in C has at least one element in common. Associate with a family of subsets C a positive(i.e.,monotone) Boolean function fc such that fc(x)= 1 if the Boolean vector x is equal to or greater than the characteristic vector of some subset in C,and 0 otherwise.It is known that C is a coterie if and only if fc is dual-minor,and is a non-dominated(ND)coterie if and only if fc is self-dual. In this paper,we introduce an operator p,which transforms a positive self-dual function into another positive self-dual function,and the concept of almost-self-duality,which is a ciose approximation to self-duality and can be checked in polynomial time(the complexity of checking positive self-duality is currently unknown).After proving several interesting properties of them,we propose a simple algorithm to check whether a given positive function is self-dual or not.Although this is not a polynomial algorithm,it is practically efficient in most cases.Finally,we present an incrementally polynomial algorithm that generates all positive self-dual functions(ND coteries)by repeatedly applying p operations. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | positive Boolean function / self-dual function / almost-self- dual function / mutual exclusion / reverse search / coterie |
Paper # | COMP94-47 |
Date of Issue |
Conference Information | |
Committee | COMP |
---|---|
Conference Date | 1994/10/21(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Theoretical Foundations of Computing (COMP) |
---|---|
Language | ENG |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Generating and Approximating Non-Dominated Coteries |
Sub Title (in English) | |
Keyword(1) | positive Boolean function |
Keyword(2) | self-dual function |
Keyword(3) | almost-self- dual function |
Keyword(4) | mutual exclusion |
Keyword(5) | reverse search |
Keyword(6) | coterie |
1st Author's Name | J.C. Bioch |
1st Author's Affiliation | Department of Computer Science,Erasmus University Rotterdam() |
2nd Author's Name | Toshihide Ibaraki |
2nd Author's Affiliation | Department of Applied Mathematics and physics,Faculty of Engineering,Kyoto University |
Date | 1994/10/21 |
Paper # | COMP94-47 |
Volume (vol) | vol.94 |
Number (no) | 304 |
Page | pp.pp.- |
#Pages | 10 |
Date of Issue |