Decomposition into two trees with orientation constraints

DOI10.1016/J.DISOPT.2013.12.002zbMATH Open1308.05100arXiv1304.3613OpenAlexW2047840586MaRDI QIDQ2339817FDOQ2339817

Olivier Durand de Gevigney

Publication date: 9 April 2015

Published in: Discrete Optimization (Search for Journal in Brave)

Abstract: We prove that deciding whether the edge set of a graph can be partitionned into two spanning trees with orientation constraints is NP-complete. If P $eq$ NP then this disproves a conjecture of Recski.

Full work available at URL: https://arxiv.org/abs/1304.3613

Recommendations

• Tree-compositions and orientations
• The decomposition of trees into subtrees
• Tree decomposition
• On the shape of decomposable trees
• Decompositions of graphs into trees
• Decomposition of some planar graphs into trees
• Orthogonal tree decompositions of graphs
• Decomposition of complete graphs into arbitrary trees
• On the decomposition dimension of trees
• Tree decomposition of graphs

zbMATH Keywords

spanning treesgraphs orientation

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• On the degrees of the vertices of a directed graph
• Title not available (Why is that?)
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• The complexity of satisfiability problems
• Title not available (Why is that?)

Cited In (2)

• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: Decomposition into two trees with orientation constraints

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