A New Algorithm for Normal Dominance Constraints

Abstract : Dominance constraints are logical descriptions of trees. Efficient algorithms for the subclass of normal dominance constraints were recently proposed. We present a new and simpler graph algorithm solving these constraints more efficiently, in quadratic time per solved form. It also applies to weakly normal dominance constraints as needed for an application to computational linguistics. Subquadratic running time can be achieved employing decremental graph biconnectivity algorithms.
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/inria-00536536
Contributor : Joachim Niehren <>
Submitted on : Thursday, November 18, 2010 - 4:36:01 PM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on : Saturday, February 19, 2011 - 2:45:17 AM

File

wndc.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00536536, version 1

Citation

Manuel Bodirsky, Denys Duchier, Joachim Niehren, Sebastian Miele. A New Algorithm for Normal Dominance Constraints. ACM-SIAM Symposium on Discrete Algorithms - SODA'2003, Jan 2004, New Orleans, Louisiana, United States. pp.59-67. ⟨inria-00536536⟩

Share

Metrics

Record views

516

Files downloads

193