New Parameterized Algorithms for APSP in Directed Graphs

DOI10.4230/LIPICS.ESA.2016.72MaRDI QIDQ4606346zbMATH OpenOpenAlexFDO

Authors Ely Porat, Eduard Shahbazian, Roei Tov

Publication date 2 March 2018

Full work available at URL https://dblp.uni-trier.de/db/conf/esa/esa2016.html#PoratST16

zbMATH Keywords

APSPdistancesfast matrix multiplicationgraphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Parameterized complexity of directed spanner problems
• Parameterized Complexity of Directed Spanner Problems.
• Parameterized algorithms for generalizations of directed feedback vertex set
• Parameterized algorithms for generalizations of directed feedback vertex set
• Parameterized complexity of directed Steiner tree on sparse graphs
• Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
• A parameterized algorithmics framework for degree sequence completion problems in directed graphs
• A parameterized algorithmics framework for degree sequence completion problems in directed graphs
• Improved approximation for the directed spanner problem
• Approximation algorithms for the directed path partition problems

This page was built for publication: New Parameterized Algorithms for APSP in Directed Graphs

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