2024/05/09 by Meike Hatzel, Hatzel, Meike, Johannes Schröder +1
Computer Science · Engineering · #Combinatorics (math.CO) #Constraint Satisfaction and Optimization #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Logic, Reasoning, and Knowledge #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2405.05571
openalex publication_date 2024/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Treewidth on undirected graphs is known to have many algorithmic applications. When considering directed width-measures there are much less results on their deployment for algorithmic results. In 2022 the first author, Rabinovich and Wiederrecht introduced a new directed width measure, S-DAG-width, using directed separations and obtained a structural duality for it. In 2012 Berwanger~et~al.~solved Parity Games in polynomial time on digraphs of bounded DAG-width. With generalising this result to digraphs of bounded S-DAG-width and also providing an algorithm to compute the S-DAG-width of a given digraphs we give first algorithmical results for this new parameter.