An Efficient Graph Algorithm for Dominance Constraints
Identifieur interne : 003A08 ( Crin/Curation ); précédent : 003A07; suivant : 003A09An Efficient Graph Algorithm for Dominance Constraints
Auteurs : Ernst Althaus ; Denys Duchier ; Alexander Koller ; Kurt Mehlhorn ; Joachim Niehren ; Sven ThielSource :
- Journal of Algorithms ; 2003.
English descriptors
- KwdEn :
Abstract
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.
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: Pour aller vers cette notice dans l'étape Curation :003A08
Links to Exploration step
CRIN:althaus03aLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="448">An Efficient Graph Algorithm for Dominance Constraints</title></titleStmt><publicationStmt><idno type="RBID">CRIN:althaus03a</idno><date when="2003" year="2003">2003</date><idno type="wicri:Area/Crin/Corpus">003A08</idno><idno type="wicri:Area/Crin/Curation">003A08</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">003A08</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">An Efficient Graph Algorithm for Dominance Constraints</title><author><name sortKey="Althaus, Ernst" sort="Althaus, Ernst" uniqKey="Althaus E" first="Ernst" last="Althaus">Ernst Althaus</name></author><author><name sortKey="Duchier, Denys" sort="Duchier, Denys" uniqKey="Duchier D" first="Denys" last="Duchier">Denys Duchier</name></author><author><name sortKey="Koller, Alexander" sort="Koller, Alexander" uniqKey="Koller A" first="Alexander" last="Koller">Alexander Koller</name></author><author><name sortKey="Mehlhorn, Kurt" sort="Mehlhorn, Kurt" uniqKey="Mehlhorn K" first="Kurt" last="Mehlhorn">Kurt Mehlhorn</name></author><author><name sortKey="Niehren, Joachim" sort="Niehren, Joachim" uniqKey="Niehren J" first="Joachim" last="Niehren">Joachim Niehren</name></author><author><name sortKey="Thiel, Sven" sort="Thiel, Sven" uniqKey="Thiel S" first="Sven" last="Thiel">Sven Thiel</name></author></analytic><series><title level="j">Journal of Algorithms</title><imprint><date when="2003" type="published">2003</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>dominance constraints</term><term>graph algorithm</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="2240">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.</div></front></TEI><BibTex type="article"><ref>althaus03a</ref><crinnumber>A03-R-279</crinnumber><category>1</category><author><e>Althaus, Ernst</e><e>Duchier, Denys</e><e>Koller, Alexander</e><e>Mehlhorn, Kurt</e><e>Niehren, Joachim</e><e>Thiel, Sven</e></author><title>An Efficient Graph Algorithm for Dominance Constraints</title><journal>Journal of Algorithms</journal><year>2003</year><volume>48</volume><number>1</number><pages>194-219</pages><month>May</month><note>Special Issue of SODA 2001.</note><keywords><e>dominance constraints</e><e>graph algorithm</e></keywords><abstract>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.</abstract></BibTex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Crin/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003A08 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Crin/Curation/biblio.hfd -nk 003A08 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Crin
|étape= Curation
|type= RBID
|clé= CRIN:althaus03a
|texte= An Efficient Graph Algorithm for Dominance Constraints
}}
| This area was generated with Dilib version V0.6.33. |  |