TY - GEN

T1 - The asynchronous committee meeting problem

AU - Esparza, Javier

AU - Von Stengel, Bernhard

N1 - Publisher Copyright:
© 1994, Springer Verlag. All rights reserved.

PY - 1994

Y1 - 1994

N2 - The committee meeting problem consists in finding the earliest meeting time acceptable to every member of a committee. We consider an asynchronous version of the problem that does not presuppose the existence of a global clock, where meeting times are maximal antichains in a poset of ‘local times’, and propose an efficient algorithm to solve it. A generalization, the private meeting problem, where the earliest time for a meeting without some committee members is sought, turns out to be NP-complete. However, it can be solved in polynomial time if the poset is N-free, that is, representing a precedence of the arcs (and not the nodes) of an acyclic directed graph. This special case is relevant, because it allows to improve the key algorithm of the model checking technique developed in [4] for Petri nets.

AB - The committee meeting problem consists in finding the earliest meeting time acceptable to every member of a committee. We consider an asynchronous version of the problem that does not presuppose the existence of a global clock, where meeting times are maximal antichains in a poset of ‘local times’, and propose an efficient algorithm to solve it. A generalization, the private meeting problem, where the earliest time for a meeting without some committee members is sought, turns out to be NP-complete. However, it can be solved in polynomial time if the poset is N-free, that is, representing a precedence of the arcs (and not the nodes) of an acyclic directed graph. This special case is relevant, because it allows to improve the key algorithm of the model checking technique developed in [4] for Petri nets.

KW - Committee meeting problem

KW - Maximal antichains

KW - N-free posets

KW - Petri net unfolding

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

U2 - 10.1007/3-540-57899-4_59

DO - 10.1007/3-540-57899-4_59

M3 - Conference contribution

AN - SCOPUS:85028472548

SN - 9783540578994

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 276

EP - 287

BT - Graph-Theoretic Concepts in Computer Science - 19th International Workshop, WG 1993, Proceedings

A2 - van Leeuwen, Jan

PB - Springer Verlag

T2 - 19th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1993

Y2 - 16 June 1993 through 18 June 1993

ER -