NDLI: Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Lingas, Andrzej Czumaj, Artur
Copyright Year	2009
Abstract	We show that a maximum-weight triangle in an undirected graph with n vertices and real weights assigned to vertices can be found in time $\mathcal{O}(n^{\omega}+n^{2+o(1)})$, where $\omega$ is the exponent of the fastest matrix multiplication algorithm. By the currently best bound on $\omega$, the running time of our algorithm is $\mathcal{O}(n^{2.376})$. Our algorithm substantially improves the previous time-bounds for this problem, and its asymptotic time complexity matches that of the fastest known algorithm for finding any triangle (not necessarily a maximum-weight one) in a graph. We can extend our algorithm to improve the upper bounds on finding a maximum-weight triangle in a sparse graph and on finding a maximum-weight subgraph isomorphic to a fixed graph. We can find a maximum-weight triangle in a vertex-weighted graph with m edges in asymptotic time required by the fastest algorithm for finding any triangle in a graph with m edges, i.e., in time $\mathcal{O}(m^{1.41})$. Our algorithms for a maximum-weight fixed subgraph (in particular any clique of constant size) are asymptotically as fast as the fastest known algorithms for a fixed subgraph.
Starting Page	431
Ending Page	444
Page Count	14
File Format	PDF
ISSN	00975397
DOI	10.1137/070695149
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	2 (Special Section on Foundations of Computer Science)
Volume Number	39
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2009-06-03
Access Restriction	Subscribed
Subject Keyword	vertex-weighted graph matrix multiplication Analysis of algorithms and problem complexity graph triangle Graphs and linear algebra time complexity General Graph theory Analysis of algorithms graph algorithms
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

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

Finding a heaviest triangle is not harder than matrix multiplication

Finding a heaviest triangle is not harder than matrix multiplication (2007)

Finding a heaviest triangle is not harder than.

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

Detecting and Counting Small Pattern Graphs

Counting and Detecting Small Subgraphs via Equations

Testing Triangle-Freeness in General Graphs

More Algorithms for All-Pairs Shortest Paths in Weighted Graphs

Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication

Similar Documents

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

Finding a heaviest triangle is not harder than matrix multiplication

Finding a heaviest triangle is not harder than matrix multiplication (2007)

Finding a heaviest triangle is not harder than.

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

Detecting and Counting Small Pattern Graphs

Counting and Detecting Small Subgraphs via Equations

Testing Triangle-Freeness in General Graphs

More Algorithms for All-Pairs Shortest Paths in Weighted Graphs

Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication