MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Althaus, Ernst
Duchier, Denys
Koller, Alexander
Mehlhorn, Kurt
Niehren, Joachim
Thiel, Sven		dblp
dblp
dblp
dblp
dblp
dblp
Editor(s):
BibTeX cite key*:
ADKMNT2001
Title, Booktitle
Title*:
An Efficient Algorithm for the Configuration Problem of Dominance Graphs
Booktitle*:
Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-01)
Event, URLs
Conference URL::
http://www.siam.org/meetings/da01
Downloading URL:
Event Address*:
Washington DC, USA
Language:
English
Event Date*
(no longer used):
January, 7 - January, 9
Organization:
ACM-SIAM
Event Start Date:
24 November 2020
Event End Date:
24 November 2020
Publisher
Name*:
ACM
URL:
Address*:
New York
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
January
Pages:
815-824
Year*:
2001
VG Wort Pages:
28
ISBN/ISSN:
0-89871-490-7
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
Dominance constraints are logical
tree descriptions originating from automata theory that have multiple
applications in computational linguistics. The satisfiability problem
of dominance constraints is NP-complete. In most applications,
however, only \emph{normal} dominance constraints are used. The
satisfiability problem of normal dominance constraints can be reduced
in linear time to the configuration problem of dominance graphs, as
shown recently. In this paper, we give a polynomial time algorithm
testing configurability of dominance graphs (and thus satisfiability
of normal dominance constraints). Previous to our work no polynomial
time algorithms were known.
HyperLinks / References / URLs:
www.mpi-sb.mpg.de/~sthiel
Download
Access Level:

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{ADKMNT2001,
AUTHOR = {Althaus, Ernst and Duchier, Denys and Koller, Alexander and Mehlhorn, Kurt and Niehren, Joachim and Thiel, Sven},
 TITLE = {An Efficient Algorithm for the Configuration Problem of Dominance Graphs},
 BOOKTITLE = {Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-01)},
 PUBLISHER = {ACM},
 YEAR = {2001},
 ORGANIZATION = {ACM-SIAM},
 PAGES = {815--824},
 ADDRESS = {Washington DC, USA},
 MONTH = {January},
 ISBN = {0-89871-490-7},
}

Entry last modified by Anja Becker, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Sven Thiel		Created
01/16/2001 09:46:59 AM
Revisions
7.
6.
5.
4.
3.		Editor(s)
Anja Becker
Anja Becker
Anja Becker
Anja Becker
Anja Becker		Edit Dates
22.03.2002 13:30:15
22.03.2002 13:25:02
22.03.2002 13:16:50
22.03.2002 12:01:24
12/02/2001 11:24:26