I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - The Asynchronous Committee Meeting Problem

Reference:

J. Esparza and B. von Stengel:. The asynchronous committee meeting problem. In Jan van Leuween, editor, Proceedings of WG '93, Graph-Theoretic in Computer Science, 19th International Workshop, number 790 in Lecture Notes in Computer Science, pages 276–287, 1993.

Abstract:

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 presupose 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 acrylic directed graph. This special case is relevant, because it allows to improve the key algorithm of the model checking technique developed in for Petri nets.

Suggested BibTeX entry:

@inproceedings{ES93,
    author = {J. Esparza and B. von Stengel:},
    booktitle = {Proceedings of WG '93, Graph-Theoretic in Computer Science, 19th International Workshop},
    editor = {Jan van Leuween},
    number = {790},
    pages = {276-287},
    series = {{Lecture Notes in Computer Science}},
    title = {The Asynchronous Committee Meeting Problem},
    year = {1993}
}

GZipped PostScript (43 kB)
PDF (179 kB)