On the problem of finding disjoint cycles and dicycles in a digraph (Q2428634): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00493-011-2670-z / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1988011810 / rank | |||
Normal rank |
Revision as of 20:26, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the problem of finding disjoint cycles and dicycles in a digraph |
scientific article |
Statements
On the problem of finding disjoint cycles and dicycles in a digraph (English)
0 references
26 April 2012
0 references
Given a digraph \(D\), the purpose of the paper is to determine whether or not there exist a cycle \(B\) in \(D\) and a cycle \(C\) in its underlying undirected graph \(UG(D)\) such that \(B\) and \(C\) are vertex-disjoint. It is known that the problem is NP-complete if a vertex \(x\) is required to be in \(C\). In the paper under review it is shown that one can decide the existence of \(B\) and \(C\) in polynomial time if \(D\) is strongly connected. The proposed methods, based on cycle transversal number \(\tau(D)\), actually find \(B\) and \(C\) in polynomial time if they exist. For \(\tau(D)\) more than 2, the paper uses McCuaig's framework on intercyclic digraphs to find these cycles. For \(\tau(D) = 2\) by using topological methods relying on Thomassen's theorem on 2-linkages in acyclic digraphs, the paper can characterize the digraphs for which the answer is ``yes''. For \(\tau(D)\) less than 2, the paper gives another independent algorithm for its solution.
0 references
disjoint cycles
0 references
dicycles
0 references