NDLI: Algorithmic Applications of Baur-Strassen’s Theorem: Shortest Cycles, Diameter, and Matchings

Content Provider	ACM Digital Library
Author	Cygan, Marek Gabow, Harold N Sankowski, Piotr
Copyright Year	2015
Abstract	Consider a directed or an undirected graph with integral edge weights from the set [-W, W], that does not contain negative weight cycles. In this article, we introduce a general framework for solving problems on such graphs using matrix multiplication. The framework is based on the usage of Baur-Strassen’s theorem and of Strojohann’s determinant algorithm. It allows us to give new and simple solutions to the following problems: Finding Shortest Cycles. We give a simple $\textit{Õ}(\textit{Wnω})$ time algorithm for finding shortest cycles in undirected and directed graphs. For directed graphs (and undirected graphs with nonnegative weights), this matches the time bounds obtained in 2011 by Roditty and Williams. On the other hand, no algorithm working in $\textit{Õ}(\textit{Wn$ ω) time was previously known for undirected graphs with negative weights. Furthermore, our algorithm for a given directed or undirected graph detects whether it contains a negative weight cycle within the same running time. Computing Diameter and Radius. We give a simple $\textit{Õ}(\textit{Wnω})$ time algorithm for computing a diameter and radius of an undirected or directed graphs. To the best of our knowledge, no algorithm with this running time was known for undirected graphs with negative weights. Finding Minimum-Weight Perfect Matchings. We present an $\textit{Õ}(\textit{Wnω})$ time algorithm for finding minimum-weight perfect matchings in undirected graphs. This resolves an open problem posted by Sankowski [2009] who presented such an algorithm but only in the case of bipartite graphs. These three problems that are solved in the full generality demonstrate the utility of this framework. Hence, we believe that it can find applications for solving larger spectra of related problems. As an illustrative example, we apply it to the problem of computing a set of vertices that lie on cycles of length at most $\textit{t},$ for some given $\textit{t}.$ We give a simple $\textit{Õ}(\textit{Wnω})$ time algorithm for this problem that improves over the $\textit{Õ}(\textit{Wnωt})$ time algorithm given by Yuster in 2011. Besides giving this flexible framework, the other main contribution of this article is the development of a novel combinatorial interpretation of the dual solution for the minimum-weight perfect matching problem. Despite the long history of the matching problem, such a combinatorial interpretation was not known previously. This result sheds a new light on the problem, as there exist many structural theorems about unweighted matchings, but almost no results that could cope with the weighted case.
Starting Page	1
Ending Page	30
Page Count	30
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/2736283
Journal	Journal of the ACM (JACM)
Volume Number	62
Issue Number	4
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-09-11
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Maximum weight matchings Diameter and radius Matrix multiplication Shortest cycle
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

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

Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings

Algorithmic applications of baur-strassen’s theorem: shortest cycles, diameter and matchings.

All pairs shortest paths using bridging sets and rectangular matrix multiplication

Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings

Algorithmic applications of baurstrassen’s theorem: Shortest cycles, diameter and matchings (2012)

Fast context-free grammar parsing requires fast boolean matrix multiplication

Graph expansion and communication costs of fast matrix multiplication

Average-case analysis of algorithms for matchings and related problems

A parallel implementation of Strassen’s matrix multiplication algorithm for wormhole-routed all-port 2D torus networks

Algorithmic Applications of Baur-Strassen’s Theorem: Shortest Cycles, Diameter, and Matchings

Similar Documents

Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings

Algorithmic applications of baur-strassen’s theorem: shortest cycles, diameter and matchings.

All pairs shortest paths using bridging sets and rectangular matrix multiplication

Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings

Algorithmic applications of baurstrassen’s theorem: Shortest cycles, diameter and matchings (2012)

Fast context-free grammar parsing requires fast boolean matrix multiplication

Graph expansion and communication costs of fast matrix multiplication

Average-case analysis of algorithms for matchings and related problems

A parallel implementation of Strassen’s matrix multiplication algorithm for wormhole-routed all-port 2D torus networks

Algorithmic Applications of Baur-Strassen’s Theorem: Shortest Cycles, Diameter, and Matchings