Better approximations for tree sparsity in nearly-linear time

DOI10.1137/1.9781611974782.145zbMATH Open1410.68394OpenAlexW4235809492MaRDI QIDQ4575893FDOQ4575893

Authors: Artūrs Bačkurs, Ludwig Schmidt, Piotr Indyk 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974782.145

Recommendations

• scientific article; zbMATH DE number 1303580
• scientific article; zbMATH DE number 1113983
• Approximating the minmax rooted-tree cover in a tree
• Sparsification and subexponential approximation
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Cited In (10)

• On sparsification for computing treewidth
• Title not available (Why is that?)
• Title not available (Why is that?)
• On integer programming and convolution
• Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems
• A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
• Bisection of bounded treewidth graphs by convolutions
• Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
• A \(\{-1,0,1\}\)- and sparsest basis for the null space of a forest in optimal time
• The tree inclusion problem

This page was built for publication: Better approximations for tree sparsity in nearly-linear time

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