{"id":"arxiv/2605.26938","url":"https://arxiv.org/abs/2605.26938","tags":["cs.AI","math.OC"],"score":0,"title":"Developing a Totally Unimodular Linear Program for Optimal Conformance Checking: When and Why It Complements A*","domain":"cs.AI","source":"arxiv","authors":["Izack Cohen"],"reviews":0,"subject":"cs.AI","summary":"Alignment-based conformance checking is the state-of-the-art approach for comparing observed process executions with normative process models. The standard exact solution relies on an A*-based heuristic search, which can exhibit exponential runtime in the presence of long traces or substantial deviations. This paper introduces a reformulation of alignment-based conformance checking as a totally unimodular linear program (LP) defined on the reachability graph of the synchronous product. By exploiting the underlying network-flow structure, the proposed formulation guarantees the existence of…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-26","reactions":{}}