The maximum binary tree problem

DOI10.1007/S00453-021-00836-5OpenAlexW3170602412MaRDI QIDQ2041978FDOQ2041978

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

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

zbMATH Keywords

fixed-parameter tractabilityinapproximabilitymaximum binary tree

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Finding and counting vertex-colored subtrees
• Narrow sieves for parameterized paths and packings
• Constrained multilinear detection and generalized graph motifs
• Faster Algebraic Algorithms for Path and Packing Problems
• Limits and Applications of Group Algebras for Parameterized Problems
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• Color-coding
• Automata, Languages and Programming
• Parameterized Algorithms
• Algorithms and Computation
• On approximating the longest path in a graph
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Bipartite permutation graphs
• On some network design problems with degree constraints
• The Traveling Salesman Problem with Distances One and Two
• Bandwidth of chain graphs
• Title not available (Why is that?)
• A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• Survivable network design with degree or order constraints
• Additive guarantees for degree-bounded directed network design
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
• What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs
• Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
• Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
• Degree-Constrained Subgraph Problems: Hardness and Approximation Results
• Subgraphs of minimal degree \(k\)
• Approximation algorithms for degree-constrained minimum-cost network-design problems
• Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal
• Heapable Sequences and Subseqeuences
• Heapability, Interactive Particle Systems, Partial Orders: Results and Open Problems
• A New Point of NP-Hardness for 2-to-1 Label Cover
• Improved inapproximability results for maximum \(k\)-colorable subgraph
• On the heapability of finite partial orders

Cited In (4)

• Title not available (Why is that?)
• Maximal flow in branching trees and binary search trees
• The Maximum Binary Tree Problem.
• 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)