Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication

DOI10.1137/070695149MaRDI QIDQ3558009zbMATH OpenOpenAlexFDO

Authors Artur Czumaj, Andrzej Lingas

Publication date 29 April 2010

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL http://wrap.warwick.ac.uk/17465/1/WRAP_Czumaj_GetPDFServlet2.pdf

zbMATH Keywords

graph algorithmsmatrix multiplicationtime complexityvertex-weighted graphgraph triangle

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)

Recommendations

• Finding a heaviest triangle is not harder than matrix multiplication
• Finding heaviest H-subgraphs in real weighted graphs, with applications
• Finding a maximum weight triangle in n ^3-Δ time, with applications
• Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems
• Finding the largest triangle in a graph in expected quadratic time

Cited in

(16)

• Fooling views: a new lower bound technique for distributed computations under congestion
• Efficient parameterized algorithms for computing all-pairs shortest paths
• Detecting and counting small pattern graphs
• Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems
• Even faster elastic-degenerate string matching via fast matrix multiplication
• Extreme witnesses and their applications
• Elastic-Degenerate String Matching via Fast Matrix Multiplication
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• Finding the largest triangle in a graph in expected quadratic time
• Extreme witnesses and their applications
• Finding heaviest H-subgraphs in real weighted graphs, with applications
• BetweenO(nm) andO(n^alpha)
• Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
• Finding a maximum weight triangle in n ^3-Δ time, with applications
• On minimum witnesses for Boolean matrix multiplication
• Finding a heaviest triangle is not harder than matrix multiplication

This page was built for publication: Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication

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