The asynchronous committee meeting problem

Javier Esparza, Bernhard Von Stengel

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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 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.

Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science - 19th International Workshop, WG 1993, Proceedings
EditorsJan van Leeuwen
PublisherSpringer Verlag
Pages276-287
Number of pages12
ISBN (Print)9783540578994
DOIs
StatePublished - 1994
Externally publishedYes
Event19th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1993 - Utrecht, Netherlands
Duration: 16 Jun 199318 Jun 1993

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume790 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference19th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1993
Country/TerritoryNetherlands
CityUtrecht
Period16/06/9318/06/93

Keywords

  • Committee meeting problem
  • Maximal antichains
  • N-free posets
  • Petri net unfolding

Fingerprint

Dive into the research topics of 'The asynchronous committee meeting problem'. Together they form a unique fingerprint.

Cite this