A note on the parameterized complexity of unordered maximum tree orientation

DOI10.1016/J.DAM.2012.02.017zbMATH Open1243.05063OpenAlexW2055745676MaRDI QIDQ427909FDOQ427909

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

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

zbMATH Keywords

graph orientationbipartizationdirected pathparameterized reduction

Mathematics Subject Classification ID

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

Cites Work

• Finding odd cycle transversals.
• Exploiting Bounded Signal Flow for Graph Orientation Based on Cause–Effect Pairs
• Approximation algorithms for orienting mixed graphs
• Title not available (Why is that?)
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Title not available (Why is that?)
• Improved upper bounds for vertex cover
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• Simpler parameterized algorithm for OCT
• A faster fixed-parameter approach to drawing binary tanglegrams

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)