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

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
• 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?)
• Title not available (Why is that?)

Cited In (1)

• Title not available (Why is that?)

Recommendations

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

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)