A note on the parameterized complexity of unordered maximum tree orientation

DOI10.1016/j.dam.2012.02.017zbMath1243.05063OpenAlexW2055745676MaRDI QIDQ427909

Peter Damaschke, Sebastian Böcker

Publication date: 18 June 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.02.017

zbMATH Keywords

directed pathgraph orientationbipartizationparameterized reduction

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Unnamed Item
• Unnamed Item
• Finding odd cycle transversals.
• Improved upper bounds for vertex cover
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• Exploiting Bounded Signal Flow for Graph Orientation Based on Cause–Effect Pairs
• Approximation Algorithms for Orienting Mixed Graphs
• Simpler Parameterized Algorithm for OCT
• A Faster Fixed-Parameter Approach to Drawing Binary Tanglegrams

This page was built for publication: A note on the parameterized complexity of unordered maximum tree orientation