A parameterized algorithmics framework for degree sequence completion problems in directed graphs
type: Item
instance of: scholarly article
title: A parameterized algorithmics framework for degree sequence completion problems in directed graphs
zbMATH Open document ID: 1421.68108
author: Robert Bredereck
author: Vincent Froese
author: Marcel Koseler
author: Marcelo Garlet Millani
author: André Nichterlein
author: Rolf Niedermeier
published in: Algorithmica
publication date: 2019-04-25T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/6935/
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7047706
zbMATH Keywords: NP-hard graph problem
zbMATH Keywords: graph realizability
zbMATH Keywords: \(k\)-anonymity
zbMATH Keywords: graph modification
zbMATH Keywords: arc insertion
zbMATH Keywords: fixed-parameter tractability
zbMATH Keywords: kernelization
MaRDI profile type: Publication
OpenAlex ID: W2964082661
cites work: Q3056948
cites work: Computational Complexity
cites work: Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
cites work: Completing orientations of partially oriented graphs
cites work: Finding large degree-anonymous subgraphs is hard
cites work: On the realization of a (p,s)-digraph with prescribed degrees
cites work: Parameterized complexity of Eulerian deletion problems
cites work: Parameterized Algorithms
cites work: Efficient Algorithms for Eulerian Extension and Rural Postman
cites work: Fundamentals of parameterized complexity
cites work: Q3287781
cites work: Parametrized complexity theory.
cites work: An application of simultaneous diophantine approximation in combinatorial optimization
cites work: Win-win kernelization for degree sequence completion problems
cites work: Zero-one matrices with zero trace
cites work: A theorem on flows in networks
cites work: Q4198056
cites work: Editing to a graph of given degrees
cites work: Graph editing to a given degree sequence
cites work: On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
cites work: NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs
cites work: A refined complexity analysis of degree anonymization in graphs
cites work: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
cites work: Minkowski's Convex Body Theorem and Integer Programming
cites work: Algorithms for constructing graphs and digraphs with given valences and factors
cites work: Integer Programming with a Fixed Number of Variables
cites work: Editing graphs to satisfy degree constraints: a parameterized approach
cites work: Parameterized complexity of finding regular induced subgraphs
cites work: Q5710169
cites work: Max flows in O(nm) time, or better
cites work: On making directed graphs transitive
Wikidata QID: Q129354246
DOI: 10.1007/S00453-018-0494-6
description: scientific article; zbMATH DE number 7047706