WFRF:(Jensen Carl)
Sökning: WFRF:(Jensen Carl) > Restricted cycle fa...
- 9 av 127
- Föregående post
- Nästa post
- Till träfflistan
Restricted cycle factors and arc-decompositions of digraphs
-
- Bang-Jensen, Jorgen (författare)
- University of Southern Denmark, Denmark
-
- Casselgren, Carl Johan (författare)
- Linköpings universitet,Matematik och tillämpad matematik,Tekniska fakulteten
- (creator_code:org_t)
- Elsevier, 2015
- 2015
- Engelska.
- Ingår i: Discrete Applied Mathematics. - : Elsevier. - 0166-218X .- 1872-6771. ; 193, s. 80-93
- Tidskriftsartikel (refereegranskat)
Abstract
Ämnesord
Stäng
- We study the complexity of finding 2-factors with various restrictions as well as edge-decompositions in (the underlying graphs of) digraphs. In particular we show that it is N P-complete to decide whether the underlying undirected graph of a digraph D has a 2-factor with cycles C-1, C-2, ..., C-k such that at least one of the cycles C-i is a directed cycle in D (while the others may violate the orientation back in D). This solves an open problem from J. Bang-Jensen et al., Vertex-disjoint directed and undirected cycles in general digraphs, JCT B 106 (2014), 1-14. Our other main result is that it is also N P-complete to decide whether a 2-edge-colored bipartite graph has two edge-disjoint perfect matchings such that one of these is monochromatic (while the other does not have to be). We also study the complexity of a number of related problems. In particular we prove that for every even k greater than= 2, the problem of deciding whether a bipartite digraph of girth k has a k-cycle-free cycle factor is N P-complete. Some of our reductions are based on connections to Latin squares and so-called avoidable arrays.
Ämnesord
- NATURVETENSKAP -- Matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics (hsv//eng)
Nyckelord
- Cycle factor; 2-factor; Mixed problem; NP-complete; Complexity; Cycle factors with no short cycles; Latin square; Avoidable arrays; Monochromatic matchings
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
- Discrete Applied Mathematics (Sök värdpublikationen i LIBRIS)
Till lärosätets databas
- 9 av 127
- Föregående post
- Nästa post
- Till träfflistan
Hitta mer i SwePub
- Av författaren/redakt...
- Bang-Jensen, Jor ...
- Casselgren, Carl ...
- Om ämnet
-
- NATURVETENSKAP
- NATURVETENSKAP
- och Matematik
- Artiklar i publikationen
- Discrete Applied ...
- Av lärosätet
- Linköpings universitet
Sök utanför SwePub
- Sök vidare i:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - Nationella bibliotekssystem
- LIBRIS.kb.se
