Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update
Options:








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

URL of the conference:

http://www.siam.org/meetings/da01

URL for downloading the paper:


Event Address*:

Washington DC, USA
Language:

English

Event Date*
(no longer used):

January, 7 - January, 9
Organization:

ACM-SIAM

Event Start Date:

16 October 2019
Event End Date:

16 October 2019

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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