English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Conference Paper

An Efficient Algorithm for the Configuration Problem of Dominance Graphs

MPS-Authors
/persons/resource/persons44003

Althaus,  Ernst
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45021

Mehlhorn,  Kurt       
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45615

Thiel,  Sven
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Althaus, E., Duchier, D., Koller, A., Mehlhorn, K., Niehren, J., & Thiel, S. (2001). An Efficient Algorithm for the Configuration Problem of Dominance Graphs. In SODA '01 (pp. 815-824). New York, NY: ACM.


Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-3136-3
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.