6533b836fe1ef96bd12a0b2d
RESEARCH PRODUCT
Efficient lower and upper bounds of the diagonal-flip distance between triangulations
Jean Marcel PalloJean-luc Barilsubject
Binary treeOpen problem010102 general mathematicsDiagonalApproximation algorithmTriangulation (social science)0102 computer and information sciences01 natural sciencesUpper and lower boundsComputer Science ApplicationsTheoretical Computer ScienceCombinatorics010201 computation theory & mathematicsTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITYSignal Processing[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]0101 mathematicsRotation (mathematics)Time complexityComputingMilieux_MISCELLANEOUSInformation SystemsMathematicsdescription
There remains today an open problem whether the rotation distance between binary trees or equivalently the diagonal-flip distance between triangulations can be computed in polynomial time. We present an efficient algorithm for computing lower and upper bounds of this distance between a pair of triangulations.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2006-11-01 |