Strong orientations without even directed circuits
| Autor: | F. B. Shepherd, A. M. H. Gerards |
|---|---|
| Rok vydání: | 1998 |
| Předmět: |
Discrete mathematics
Strongly connected component 010102 general mathematics 0102 computer and information sciences Directed graph 01 natural sciences Longest path problem Theoretical Computer Science Modular decomposition Combinatorics Indifference graph Pathwidth Strong connectivity 010201 computation theory & mathematics Chordal graph Orientation Robbins' theorem 05C20 05C75 Discrete Mathematics and Combinatorics 0101 mathematics Signed graphs MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Discrete Mathematics, 188(1-3), 111-125. Elsevier |
| ISSN: | 0012-365X |
| DOI: | 10.1016/s0012-365x(97)00247-1 |
| Popis: | We characterize the graphs for which all 2-connected non-bipartite subgraphs have a strongly connected orientation in which each directed circuit has an odd number of edges. We also give a polynomial-time algorithm to find such an orientation in these graphs. Moreover, we give an algorithm that given any orientation of such a graph, determines if it has an even directed circuit. The proofs of these results are based on a constructive characterization of these graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect