Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems

DOI10.1007/11786986_24MaRDI QIDQ3613765zbMATH OpenOpenAlexFDO

Authors Raphael Yuster, Virginia Vassilevska Williams, Ryan Williams

Publication date 12 March 2009

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11786986_24

zbMATH Keywords

algorithmedge weigted graphsfast matrix multiplicationminimum weight subgraphrectangular matrix multiplicationsmallest cyclevertex weighted graphsweighted graphs

Mathematics Subject Classification ID

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

Recommendations

• Finding heaviest H-subgraphs in real weighted graphs, with applications
• Finding, minimizing, and counting weighted subgraphs
• Finding, minimizing, and counting weighted subgraphs
• Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
• Finding a heaviest triangle is not harder than matrix multiplication

Cited in

(12)

• Finding, minimizing, and counting weighted subgraphs
• Finding a heaviest triangle is not harder than matrix multiplication
• Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
• scientific article; zbMATH DE number 139776 (Why is no real title available?)
• Improved time bounds for all pairs non-decreasing paths in general digraphs
• Finding, minimizing, and counting weighted subgraphs
• Exact weight subgraphs and the k-sum conjecture
• Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
• All-pairs bottleneck paths in vertex weighted graphs
• Finding heaviest H-subgraphs in real weighted graphs, with applications
• Algorithms, reductions and equivalences for small weight variants of all-pairs shortest paths
• Efficient approximation algorithms for shortest cycles in undirected graphs

This page was built for publication: Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems

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