Restricted cycle factors and arc-decompositions of digraphs

DOI10.1016/j.dam.2015.04.020zbMath1317.05068OpenAlexW1659291953MaRDI QIDQ2354716

Carl Johan Casselgren, Jörgen Bang-Jensen

Publication date: 24 July 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-120854

zbMATH Keywords

complexity2-factormixed problemLatin squareNP-completecycle factormonochromatic matchingsavoidable arrayscycle factors with no short cycles

Mathematics Subject Classification ID

Paths and cycles (05C38) Orthogonal arrays, Latin squares, Room squares (05B15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)

Related Items (1)

Lexicographic Orientation Algorithms

Cites Work

• Vertex-disjoint directed and undirected cycles in general digraphs
• On avoiding some families of arrays
• On the problem of finding disjoint cycles and dicycles in a digraph
• Finding maximum square-free 2-matchings in bipartite graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• NP completeness of the edge precoloring extension problem on bipartite graphs
• Digraphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Restricted cycle factors and arc-decompositions of digraphs