A parameterized algorithmics framework for degree sequence completion problems in directed graphs
DOI10.1007/s00453-018-0494-6zbMath1421.68108OpenAlexW2964082661WikidataQ129354246 ScholiaQ129354246MaRDI QIDQ1739111
Marcel Koseler, Rolf Niedermeier, Vincent Froese, Robert Bredereck, Marcelo Garlet Millani, André Nichterlein
Publication date: 25 April 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/6935/
fixed-parameter tractabilitykernelization\(k\)-anonymitygraph modificationgraph realizabilityarc insertionNP-hard graph problem
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Win-win kernelization for degree sequence completion problems
- Fundamentals of parameterized complexity
- Editing graphs to satisfy degree constraints: a parameterized approach
- On making directed graphs transitive
- Graph editing to a given degree sequence
- A theorem on flows in networks
- Zero-one matrices with zero trace
- Parameterized complexity of finding regular induced subgraphs
- An application of simultaneous diophantine approximation in combinatorial optimization
- On the realization of a (p,s)-digraph with prescribed degrees
- A refined complexity analysis of degree anonymization in graphs
- Editing to a graph of given degrees
- Parameterized complexity of Eulerian deletion problems
- Parametrized complexity theory.
- Algorithms for constructing graphs and digraphs with given valences and factors
- Integer Programming with a Fixed Number of Variables
- Minkowski's Convex Body Theorem and Integer Programming
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- Completing orientations of partially oriented graphs
- Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
- Efficient Algorithms for Eulerian Extension and Rural Postman
- Computational Complexity
- Max flows in O(nm) time, or better
- Parameterized Algorithms
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs
- Finding large degree-anonymous subgraphs is hard
This page was built for publication: A parameterized algorithmics framework for degree sequence completion problems in directed graphs
