On the parallel complexity of constrained read-once refutations in UTVPI constraint systems

DOI10.1007/978-3-031-20350-3_24OpenAlexW4313349087MaRDI QIDQ6111967

K. Subramani and Vahan Mkrtchyan, Piotr J. Wojciechowski

Publication date: 4 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-20350-3_24

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A combinatorial certifying algorithm for linear feasibility in UTVPI constraints
• Matching is as easy as matrix inversion
• A certifying algorithm for lattice point feasibility in a system of UTVPI constraints
• A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• Scaling Algorithms for Weighted Matching in General Graphs
• NC Algorithms for Weighted Planar Perfect Matching and Related Problems
• Bipartite Perfect Matching in Pseudo-Deterministic NC
• Planar Graph Perfect Matching Is in NC
• Bipartite perfect matching is in quasi-NC
• Frontiers of Combining Systems
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: On the parallel complexity of constrained read-once refutations in UTVPI constraint systems