2 papers
cs.DS2026
Planarizing Gadgets for (k, l)-tight Graphs Do Not Exist
Archit Chauhan, Rohit Gurjar, Kilian Rothmund +1
The problem of recognizing (k, l)-tight graphs is a fundamental problem that has close connections to well studied problems like graph rigidity. The problem is better understood fo…
cs.DS2025
Parallel Complexity of Depth-First-Search and Maximal path in restricted graph classes
Archit Chauhan, Samir Datta, M. Praveen
Constructing a Depth First Search (DFS) tree is a fundamental graph problem, whose parallel complexity is still not settled. Reif showed parallel intractability of lex-first DFS. I…