Restricted cycle factors and arc-decompositions of digraphs

DOI10.1016/j.dam.2015.04.020zbMath1317.05068MaRDI 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

complexity; 2-factor; mixed problem; Latin square; NP-complete; cycle factor; monochromatic matchings; avoidable arrays; cycle factors with no short cycles

Mathematics Subject Classification ID

05C38: Paths and cycles

05B15: Orthogonal arrays, Latin squares, Room squares

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C20: Directed graphs (digraphs), tournaments

Related Items

Lexicographic Orientation Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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