Cover Image

A Polynomial-time Algorithm for Detecting the Possibility of Braess Paradox in Directed Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cenciarelli, Pietro, Gorla, Daniele, Salvo, Ivano
Format:	Preprint
Published:	2016
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
by: Chen, Kuowen, et al.
Published: (2025)

A Polynomial time Algorithm for 3SAT
by: Du, Lizhi
Published: (2010)

Approximate Model Counting, Sparse XOR Constraints and Minimum Distance
by: Boreale, Michele, et al.
Published: (2019)

Graph Theoretic Investigations on Inefficiencies in Network Models
by: Cenciarelli, Pietro, et al.
Published: (2016)

Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication
by: Bentert, Matthias, et al.
Published: (2024)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
by: Ashvinkumar, Vikrant, et al.
Published: (2024)

Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
by: Karczmarz, Adam, et al.
Published: (2025)

A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
by: S, Ajaykrishnan E, et al.
Published: (2025)

Branch-and-Bound Algorithms as Polynomial-time Approximation Schemes
by: Encz, Koppány István, et al.
Published: (2025)

Counting and Sampling Labeled Chordal Graphs in Polynomial Time
by: Hebert-Johnson, Ursula, et al.
Published: (2023)

Sampling Unlabeled Chordal Graphs in Expected Polynomial Time
by: Hébert-Johnson, Úrsula, et al.
Published: (2025)

Polynomial-Time Algorithms for Weaver's Discrepancy Problem in a Dense Regime
by: Jourdan, Ben, et al.
Published: (2024)

Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
by: Bampis, Evripidis, et al.
Published: (2025)

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
by: Saxena, Raghuvansh R., et al.
Published: (2024)

Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime
by: Aggarwal, Divesh, et al.
Published: (2024)

Tree Proof-of-Position Algorithms
by: Kharman, Aida Manzano, et al.
Published: (2024)

A Polynomial Time Algorithm for Steiner Tree when Terminals Avoid a $K_4$-Minor
by: Groenland, Carla, et al.
Published: (2024)

Optimizing Distances for Multi-Broadcast in Temporal Graphs
by: Carnevale, Daniele, et al.
Published: (2026)

A Simplified Parameterized Algorithm for Directed Feedback Vertex Set
by: Xiong, Ziliang, et al.
Published: (2024)

Near-Optimal Algorithm for Directed Expander Decompositions
by: Sulser, Aurelio L., et al.
Published: (2024)

Spectral Clustering in Birthday Paradox Time
by: Kapralov, Michael, et al.
Published: (2026)

Faster Algorithms for Graph Monopolarity
by: Philip, Geevarghese, et al.
Published: (2024)

New Parallel and Streaming Algorithms for Directed Densest Subgraph
by: Mitrović, Slobodan, et al.
Published: (2025)

From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
by: Chekuri, Chandra, et al.
Published: (2024)

Pointwise Lipschitz Continuous Graph Algorithms
by: Liu, Quanquan C., et al.
Published: (2024)

Succinct Graph Representations and Algorithmic Applications
by: Ullah, Ahammed, et al.
Published: (2026)

Smoothed Analysis of Dynamic Graph Algorithms
by: Meir, Uri, et al.
Published: (2025)

Estimating Random-Walk Probabilities in Directed Graphs
by: Bertram, Christian, et al.
Published: (2025)

On Incremental Approximate Shortest Paths in Directed Graphs
by: Górkiewicz, Adam, et al.
Published: (2025)

Graph-Based Algorithms for Diverse Similarity Search
by: Anand, Piyush, et al.
Published: (2025)

Fast Algorithms for Graph Arboricity and Related Problems
by: Cen, Ruoxu, et al.
Published: (2025)

Improved Algorithms for Effective Resistance Computation on Graphs
by: Yang, Yichun, et al.
Published: (2025)

Efficient Kernelization Algorithm for Bipartite Graph Matching
by: Wu, Guang, et al.
Published: (2024)

A Polynomial Decision for 3-SAT
by: Weiss, Angela
Published: (2022)

Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs
by: Zhao, Yibin
Published: (2025)

PageRank Centrality in Directed Graphs with Bounded In-Degree
by: Thorup, Mikkel, et al.
Published: (2025)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
by: Hwang, Samuel, et al.
Published: (2024)

A Faster Algorithm for Maximum Weight Matching on Unrestricted Bipartite Graphs
by: Kwok, Shawxing
Published: (2025)

Scalable Algorithms for 2-Packing Sets on Arbitrary Graphs
by: Borowitz, Jannick, et al.
Published: (2023)

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
by: Assadi, Sepehr, et al.
Published: (2026)