The Maximum Binary Tree Problem.

DOI10.4230/LIPICS.ESA.2020.30OpenAlexW3081912664MaRDI QIDQ5874498FDOQ5874498

Authors Karthekeyan Chandrasekaran, Elena Grigorescu, Shubhang Kulkarni, Young-San Lin, Minshen Zhu, Gabriel Istrate 

Publication date 7 February 2023

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2020/12896/pdf/LIPIcs-ESA-2020-30.pdf/

zbMATH Keywords

fixed-parameter tractabilityinapproximabilitymaximum binary treeheapability

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• The maximum binary tree problem
• scientific article; zbMATH DE number 1253054
• Maximal path length of binary trees
• The \(p\)-maxian problem on a tree
• Maximal covering tree problems
• Binary trees with the largest number of subtrees
• The maximum utilization subtree problem
• Trees with maximum number of maximal matchings
• The number of maximum matchings in a tree
• scientific article; zbMATH DE number 644325

Cites work

• scientific article; zbMATH DE number 5158511 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• A New Point of NP-Hardness for 2-to-1 Label Cover
• A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
• Additive guarantees for degree-bounded directed network design
• Algorithms and Computation
• Approximating minimum bounded degree spanning trees to within one of optimal
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Approximation algorithms for degree-constrained minimum-cost network-design problems
• Automata, Languages and Programming
• Bandwidth of chain graphs
• Bipartite permutation graphs
• Color-coding
• Degree-Constrained Subgraph Problems: Hardness and Approximation Results
• Faster Algebraic Algorithms for Path and Packing Problems
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Heapability, interactive particle systems, partial orders: results and open problems
• Heapable sequences and subsequences
• Improved inapproximability results for maximum \(k\)-colorable subgraph
• Limits and Applications of Group Algebras for Parameterized Problems
• Narrow sieves for parameterized paths and packings
• On approximating the longest path in a graph
• On some network design problems with degree constraints
• On the heapability of finite partial orders
• Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
• Parameterized algorithms
• Subgraphs of minimal degree \(k\)
• What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs

Cited in

(3)

• scientific article; zbMATH DE number 5016713 (Why is no real title available?)
• Maximal flow in branching trees and binary search trees
• The Multi-Tier Tree Problem

This page was built for publication: The Maximum Binary Tree Problem.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874498)