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 - https://www.scopus.com/pages/publications/85028472548
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 -