> Details

Chandrasekaran, Karthekeyan [Author]; Grigorescu, Elena [Author]; Istrate, Gabriel [Author]; Kulkarni, Shubhang [Author]; Lin, Young-San [Author]; Zhu, Minshen [Author] ; Karthekeyan Chandrasekaran and Elena Grigorescu and Gabriel Istrate and Shubhang Kulkarni and Young-San Lin and Minshen Zhu [Contributor]

Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree

Reference
management

Bookmarks

Remove from
bookmarks

Share this on Whatsapp

Close

Bookmarks



You can manage bookmarks using lists, please log in to your user account for this.
  • Media type: Electronic Conference Proceeding; Text; E-Article
  • Title: Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree
  • Contributor: Chandrasekaran, Karthekeyan [Author]; Grigorescu, Elena [Author]; Istrate, Gabriel [Author]; Kulkarni, Shubhang [Author]; Lin, Young-San [Author]; Zhu, Minshen [Author]
  • imprint: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020
  • Language: English
  • DOI: https://doi.org/10.4230/LIPIcs.IPEC.2020.7
  • Keywords: maximum binary tree ; permutation directed acyclic graphs ; heapability
  • Origination:
  • Footnote: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Description: A heapable sequence is a sequence of numbers that can be arranged in a min-heap data structure. Finding a longest heapable subsequence of a given sequence was proposed by Byers, Heeringa, Mitzenmacher, and Zervas (ANALCO 2011) as a generalization of the well-studied longest increasing subsequence problem and its complexity still remains open. An equivalent formulation of the longest heapable subsequence problem is that of finding a maximum-sized binary tree in a given permutation directed acyclic graph (permutation DAG). In this work, we study parameterized algorithms for both longest heapable subsequence and maximum-sized binary tree. We introduce alphabet size as a new parameter in the study of computational problems in permutation DAGs and show that this parameter with respect to a fixed topological ordering admits a complete characterization and a polynomial time algorithm. We believe that this parameter is likely to be useful in the context of optimization problems defined over permutation DAGs.
  • Access State: Open Access