Parameterized orientable deletion

DOI10.4230/LIPICS.SWAT.2018.24MaRDI QIDQ5116488zbMATH OpenFDO

Authors Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, Florian Sikora

Publication date 25 August 2020

zbMATH Keywords

treewidthFPT algorithmsgraph orientationsSETH

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Parameterized orientable deletion
• Chordal deletion is fixed-parameter tractable
• Chordal Deletion Is Fixed-Parameter Tractable
• On bounded-degree vertex deletion parameterized by treewidth
• A parameterized algorithm for bounded-degree vertex deletion

Cites work

• scientific article; zbMATH DE number 6783432 (Why is no real title available?)
• A faster parameterized algorithm for pseudoforest deletion
• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• Degree-constrained graph orientation: maximum satisfaction and minimum violation
• Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
• GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
• Generalized pseudoforest deletion: algorithms and uniform kernel
• Graph balancing: a special case of scheduling unrelated parallel machines
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• Graph structure and monadic second-order logic. A language-theoretic approach
• MaxMin allocation via degree lower-bounded arborescences
• On allocating goods to maximize fairness
• On bounded-degree vertex deletion parameterized by treewidth
• On the configuration-LP for scheduling on unrelated machines
• Parameterized algorithms
• Planar orientations with low out-degree and compaction of adjacency matrices
• The parameterized complexity of editing graphs for bounded degeneracy
• Which problems have strongly exponential complexity?

Cited in

(8)

• Grundy Distinguishes Treewidth from Pathwidth
• Generalized cuckoo hashing with a stash, revisited
• SEF view deletion under bounded condition
• SSE and SSD: page-efficient searchable symmetric encryption
• Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
• Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
• Parameterized orientable deletion
• scientific article; zbMATH DE number 7764100 (Why is no real title available?)

This page was built for publication: Parameterized orientable deletion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116488)