Parallel Complexity of Depth-First-Search and Maximal path in restricted graph classes

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chauhan, Archit, Datta, Samir, Praveen, M.
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Complexity F.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Planarizing Gadgets for (k, l)-tight Graphs Do Not Exist
by: Chauhan, Archit, et al.
Published: (2026)

The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs
by: Chauhan, Archit, et al.
Published: (2024)

Complexity of Finding and Enumerating Interconnection Trees
by: Demange, Noé, et al.
Published: (2026)

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
by: Krithika, R., et al.
Published: (2023)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
by: Lokshtanov, Daniel, et al.
Published: (2024)

Certificate-Sensitive Subset Sum: Realizing Instance Complexity
by: Salas, Jesus
Published: (2025)

Identity Testing for Circuits with Exponentiation Gates
by: Li, Jiatu, et al.
Published: (2025)

Towards universally optimal sorting algorithms
by: Sen, Sandeep
Published: (2025)

Spanning Trees Minimizing Branching Costs
by: Gargano, Luisa, et al.
Published: (2024)

An Algorithm for a Variation of the Shortest Common Superstring Problem
by: Gilfanov, Arthur
Published: (2024)

SARRIGUREN: a polynomial-time complete algorithm for random $k$-SAT with relatively dense clauses
by: Sarriguren, Alfredo Goñi
Published: (2024)

Revisiting Tree Canonization using polynomials
by: Arvind, V., et al.
Published: (2024)

The Complexity of Maximal Common Subsequence Enumeration
by: Buzzega, Giovanni, et al.
Published: (2025)

Realizing temporal graphs from fastest travel times
by: Klobas, Nina, et al.
Published: (2023)

Approximate all-pairs Hamming distances and 0-1 matrix multiplication
by: Kowaluk, Miroslaw, et al.
Published: (2025)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
by: Kluk, Kacper, et al.
Published: (2025)

Complexity of Local Search for Euclidean Clustering Problems
by: Manthey, Bodo, et al.
Published: (2023)

The Query Complexity of Local Search and Brouwer in Rounds
by: Brânzei, Simina, et al.
Published: (2020)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
by: Saha, Barna, et al.
Published: (2024)

The Query Complexity of Local Search in Rounds on General Graphs
by: Brânzei, Simina, et al.
Published: (2026)

An Optimal Randomized Algorithm for Finding the Saddlepoint
by: Dallant, Justin, et al.
Published: (2024)

A Decomposition Approach to the Weighted $k$-server Problem
by: Ayyadevara, Nikhil, et al.
Published: (2024)

Maximization of Approximately Submodular Functions
by: Horel, Thibaut, et al.
Published: (2024)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

On Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds in the MPC Model
by: Lingas, Andrzej
Published: (2026)

Precoloring extension with demands on paths
by: Das, Arun Kumar, et al.
Published: (2025)

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
by: Kumar, Mrinal, et al.
Published: (2024)

Max-Cut with $ε$-Accurate Predictions
by: Cohen-Addad, Vincent, et al.
Published: (2024)

Graph Threading with Turn Costs
by: Demaine, Erik D., et al.
Published: (2024)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
by: Dvořák, Pavel, et al.
Published: (2017)

A Piecewise Approach for the Analysis of Exact Algorithms
by: Clinch, Katie, et al.
Published: (2024)

Minimizing Envy and Maximizing Happiness in Graphical House Allocation
by: Dhar, Anubhav, et al.
Published: (2025)

Submodular Maximization under Supermodular Constraint: Greedy Guarantees
by: Srivastava, Ajitesh, et al.
Published: (2026)

When Votes Change and Committees Should (Not)
by: Bredereck, Robert, et al.
Published: (2020)

Fair Vertex Problems Parameterized by Cluster Vertex Deletion
by: Masařík, Tomáš, et al.
Published: (2025)

A Parameterized Complexity Analysis of Bounded Height Depth-first Search Trees
by: Jaffke, Lars, et al.
Published: (2025)

Optimal Parallel Basis Finding in Graphic and Related Matroids
by: Khanna, Sanjeev, et al.
Published: (2025)

Replicability in High Dimensional Statistics
by: Hopkins, Max, et al.
Published: (2024)

The Simultaneous Triple Product Property and Group-theoretic Results for the Exponent of Matrix Multiplication
by: Murthy, Sandeep
Published: (2007)

Isometric path complexity of graphs
by: Chakraborty, Dibyayan, et al.
Published: (2022)