A note on the parameterized complexity of unordered maximum tree orientation

DOI10.1016/J.DAM.2012.02.017MaRDI QIDQ427909zbMATH OpenOpenAlexFDO

Authors 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

graph orientationbipartizationdirected pathparameterized reduction

Mathematics Subject Classification ID

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

Recommendations

• Parameterized maximum path coloring
• The parameterized complexity of oriented colouring
• Parameterized maximum path coloring
• Exact algorithms for computing the tree edit distance between unordered trees
• Approximation algorithms and hardness results for shortest path based graph orientations

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A faster fixed-parameter approach to drawing binary tanglegrams
• Approximation algorithms for orienting mixed graphs
• 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
• Finding odd cycle transversals.
• Improved upper bounds for vertex cover
• Simpler parameterized algorithm for OCT

Cited in

(1)

• On the complexity of labeled oriented trees

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

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