Finding heaviest H-subgraphs in real weighted graphs, with applications

DOI10.1145/1798596.1798597MaRDI QIDQ6486945zbMATH OpenOpenAlexFDO

Authors Virginia Vassilevska Williams, Ryan Williams, Raphael Yuster

Publication date 18 November 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1798596.1798597

zbMATH Keywords

matrix multiplicationweighted graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Recommendations

• Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
• Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems
• Finding a heaviest triangle is not harder than matrix multiplication
• Finding a maximum weight triangle in n ^3-Δ time, with applications
• Finding, minimizing, and counting weighted subgraphs

Cited in

(18)

• Finding, minimizing, and counting weighted subgraphs
• Fast monotone summation over disjoint sets
• Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
• Counting Homomorphic Cycles in Degenerate Graphs
• Computing the rooted triplet distance between galled trees by counting triangles
• Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems
• Extreme witnesses and their applications
• Induced subgraph isomorphism: are some patterns substantially easier than others?
• Quantum and approximation algorithms for maximum witnesses of Boolean matrix products
• Finding the largest triangle in a graph in expected quadratic time
• Extreme witnesses and their applications
• Sequential Monte Carlo for maximum weight subgraphs with application to solving image jigsaw puzzles
• Finding, minimizing, and counting weighted subgraphs
• Quantum and approximation algorithms for maximum witnesses of Boolean matrix products
• Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
• Exact weight subgraphs and the \(k\)-sum conjecture
• On minimum witnesses for Boolean matrix multiplication
• Finding a heaviest triangle is not harder than matrix multiplication

This page was built for publication: Finding heaviest \(H\)-subgraphs in real weighted graphs, with applications

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