Althaus, Ernst
[VerfasserIn];
Duchier, Denys
[VerfasserIn];
Koller, Alexander
[VerfasserIn];
Mehlhorn, Kurt
[VerfasserIn];
Niehren, Joachim
[VerfasserIn];
Thiel, Sven
[VerfasserIn]
An efficient graph algorithm for dominance constraints
Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
Medientyp:
E-Artikel
Titel:
An efficient graph algorithm for dominance constraints
Beteiligte:
Althaus, Ernst
[VerfasserIn];
Duchier, Denys
[VerfasserIn];
Koller, Alexander
[VerfasserIn];
Mehlhorn, Kurt
[VerfasserIn];
Niehren, Joachim
[VerfasserIn];
Thiel, Sven
[VerfasserIn]
Erschienen:
Scientific publications of the Saarland University (UdS), 2003
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify normal dominance constraints and present an efficient graph algorithm for testing their satisfiablity in deterministic polynomial time. Previously, no polynomial time algorithm was known.