The maximum binary tree problem

DOI10.1007/S00453-021-00836-5MaRDI QIDQ2041978zbMATH OpenOpenAlexFDO

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

Publication date 26 July 2021

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.07915, https://drops.dagstuhl.de/opus/volltexte/2020/12896/

zbMATH Keywords

fixed-parameter tractabilityinapproximabilitymaximum binary tree

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Recommendations

• On the approximability of some Maximum Spanning Tree Problems
• Approximating Optimal Binary Decision Trees
• On the approximability of some maximum spanning tree problems
• scientific article; zbMATH DE number 1303580
• Maximal path length of binary trees

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
• Constrained multilinear detection and generalized graph motifs
• Degree-Constrained Subgraph Problems: Hardness and Approximation Results
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• Faster Algebraic Algorithms for Path and Packing Problems
• Finding and counting vertex-colored subtrees
• 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
• Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
• Subgraphs of minimal degree \(k\)
• Survivable network design with degree or order constraints
• The Traveling Salesman Problem with Distances One and Two
• What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs

Cited in

(4)

• The Maximum Binary Tree Problem.
• 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 Q2041978)