Better approximations for tree sparsity in nearly-linear time

DOI10.1137/1.9781611974782.145MaRDI QIDQ4575893zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(9)

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

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)