Decomposition into two trees with orientation constraints

DOI10.1016/J.DISOPT.2013.12.002MaRDI QIDQ2339817zbMATH OpenOpenAlexFDO

Authors Olivier Durand de Gevigney

Publication date 9 April 2015

Published in Discrete Optimization (Search for Journal in Brave)

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

zbMATH Keywords

graphs orientationspanning trees

Mathematics Subject Classification ID

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

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.

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

Cites work

• Connections in combinatorial optimization
• Edge-Disjoint Spanning Trees of Finite Graphs
• scientific article; zbMATH DE number 3313442 (Why is no real title available?)
• On the degrees of the vertices of a directed graph
• On the Problem of Decomposing a Graph into n Connected Factors
• The complexity of satisfiability problems

Cited in

(2)

• scientific article; zbMATH DE number 20617 (Why is no real title available?)
• scientific article; zbMATH DE number 672025 (Why is no real title available?)

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)