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

DOI10.1137/070695149zbMATH Open1200.68123OpenAlexW2018033449MaRDI QIDQ3558009FDOQ3558009

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

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

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)

Cited In (16)

• Finding heaviest \(H\)-subgraphs in real weighted graphs, with applications
• 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
• 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
• Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
• BetweenO(nm) andO(n^alpha)
• Finding a maximum weight triangle in n ^3-Δ time, with applications
• Title not available (Why is that?)
• 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)