A Parameterized Algorithmics Framework for Degree Sequence Completion Problems in Directed Graphs

DOI10.4230/LIPIcs.IPEC.2016.10zbMath1398.68219arXiv1604.06302OpenAlexW2904345017MaRDI QIDQ4634393

Rolf Niedermeier, Robert Bredereck, Marcelo Garlet Millani, Marcel Koseler, Vincent Froese, André Nichterlein

Publication date: 10 April 2018

Full work available at URL: https://arxiv.org/abs/1604.06302

zbMATH Keywords

fixed-parameter tractabilitykernelizationgraph modificationgraph realizabilityarc insertionNP-hard graph problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20) Vertex degrees (05C07)

This page was built for publication: A Parameterized Algorithmics Framework for Degree Sequence Completion Problems in Directed Graphs