Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity

DOI10.1007/s00453-017-0399-9zbMath1393.68067WikidataQ59567349 ScholiaQ59567349MaRDI QIDQ724225

Hans L. Bodlaender, Hirotaka Ono, Yota Otachi

Publication date: 25 July 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6789/

zbMATH Keywords

orientation; parameterized complexity; graph class; width parameter

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C85: Graph algorithms (graph-theoretic aspects)

05C20: Directed graphs (digraphs), tournaments

05C07: Vertex degrees