From the Even Cycle Mystery to the L-Matrix Problem and Beyond

Bassett, Lowell, John Maybee, James Quirk, Qualitative Economics and the Scope of the Correspondence Principle. Econometrica, 36 (1968) 544-563.

Bondy, John A. and U. S. R. Murty, Graph Theory with Applications. MacMillan, London, 1976.

Brualdi, Richard A. and Bryan L. Shader, Matrices of Sign-Solvable Linear Systems. Cambridge University Press, 1995.

Bermond, J. C. and Carsten Thomassen, Cycles in Digraphs - A Survey. J. Graph Theory, 5 (1981) 1-43.

Chung, F. R. K., Wayne Goddard, and Daniel J. Kleitman, Even Cycles in Directed Graphs. SIAM J. Discrete Math., 7 (1994) 474-483.

Fortune, Steven, John Hopcroft, and James Wyllie, The Directed Subgraph Homeomorphism Problem. Theoretical Computer Science, 10 (1980) 111-121.

Friedland, Shmuel, Every 7-Regular Digraph Contains an Even Cycle. J. Combinatorial Theory B, 46 (1989) 249-252.

Garey, Michael R. and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., San Francisco, 1979.

Gallucio, Anna and Marin Loebl, Even Cycles and H-Homeomorphisms. To appear, 1996.

Gallucio, Anna and Marin Loebl, Even Directed Cycles in H-Free Digraphs. J. Algorithms, to appear, 1995.

Gallucio, Anna and Marin Loebl, Even/Odd Dipaths in Planar Digraphs. Optimization Methods and Software, 3 (1994) 225-236.

Harary, Frank, Graph Theory. Addison-Wesley Publishing Co., Reading, Massachusetts, 1969.

Karmarkar, S. B., An Algorithm for Finding a Circuit of Even Length in a Directed Graph. International J. Systems Sci., 15 (1984) 1197-1201.

Kasteleyn, P. W., Graph Theory and Crystal Physics. Graph Theory and Theoretical Physics, Frank Harary, ed. Academic Press, New York, 1967, 43-110.

Klee, Victor, Recursive Structure of S-Matrices and an O(m²) Algorithm for Recognizing Strong Sign-Solvability. Linear Algebra and its Applications, 96 (1987) 233-247.

Klee, Victor, Sign-patterns and Stability. Applications of Combinatorics and Graph Theory to the Biological and Social Sciences, F. Roberts, ed. IMA Volumes in Mathematics and Its Applications, Springer, New York, 17 (1989) 203-219.

Klee, Victor, The Even Cycle Mystery, the L-Matrix Problem, and Their Relatives. Unpublished manuscript, n.d.

Klee, Victor, and Michael Brundage, From The Even Cycle Mystery to the L-Matrix Problem and Beyond. To appear, 1997.

Klee, Victor and Richard Ladner, Qualitative Matrices: Strong Sign-solvability and Weak Satisfiability. Computer-Assisted Analysis and Model Simplification, H. Greenberg and J. Maybee, eds. Academic Press, New York, 1981, 293-320.

Klee, Victor, Richard Ladner, Rachel Manber, Signsolvability Revisited. Linear Algebra and its Applications, 59 (1984) 131-157.

Klee, Victor, Balder Von Hohenbalken, Ted Lewis, On the Recognition of S-Systems. Linear Algebra and its Applications, 192 (1993) 187-204.

Knuth, Donald E., A Permanent Inequality. American Math. Monthly, (1981) 731-740.

Knuth, Donald E., Overlapping Pfaffians. Electronic Journal of Combinatorics, Foata Festschrift, 3 (1995) 1-13. Available at http://ejc.math.gatech.edu/Journal/Volume_3/foatatoc.html

Koh, Khee Meng, Even Circuits in Directed Graphs and Lovasz's Conjecture. Bull. Malaysian Math. Soc., 7 (1976) 47-52.

Kucera, Ludek, Combinatorial Algorithms. Adam Hilger, Philadelphia, 1990.

LaPaugh, Andrea S. and Christos H. Papadimitriou, The Even-Path Problem for Graphs and Digraphs. Networks, 14 (1984) 507-513.

Lint, J. H. van and R. M. Wilson, A Course in Combinatorics. Cambridge University Press, 1992.

Little, C. H. C., An Extension of Kasteleyn's Method of Enumerating the 1-factors of Planar Graphs. Combinatorial Mathematics, Proceedings 2nd Australian Conference, D. Holton, ed. Lecture Notes in Mathematics 403, Springer, Berlin, 1974, 63-72.

Manber, Rachel, Graph-Theoretical Approach to Qualitative Solvability of Linear Systems. Linear Algebra and its Applications, 48 (1982) 457-470.

Maybee, John and James Quirk, Qualitative Problems in Matrix Theory. SIAM Review, 11 (1969) 30-51.

Poljak, S. and J. Rohn, Checking Robust Nonsingularity is NP-Hard. Math. Control Signals Systems, 6 (1993) 1-9.

Polya, G., Aufgabe 424. Arch. Math. Phys., 30 (1913) 271.

Quirk, James and R. Ruppert, Qualitative economics and the stability of equilibrium. Rev. Economic Studies, 32 (1965) 311-326.

Robinson, D. F. and L. R. Foulds, Digraphs: Theory and Techniques. Gordon and Breach Science Publishers, New York, 1960.

Rohn, Jiri, Systems of Linear Interval Equations. Linear Algebra and its Applications, 126 (1989) 39-78.

Rohn, Jiri, Interval Matrices: Singularity and Real Eigenvalues. SIAM J. Matrix Anal. Appl., 14 (1993) 82-91.

Seymour, P. and Carsten Thomassen, Characterization of Even Directed Graphs. J. Combinatorial Theory B, 42 (1987) 36-45.

Tarjan, Robert, Depth-First Search and Linear Graph Algorithms. SIAM J. Computing, 1 (1972) 146-160.

Thomassen, Carsten, Even Cycles in Directed Graphs. European J. Combinatorics, 6 (1985) 85-89.

Thomassen, Carsten, Sign-Nonsignular Matrices and Even Cycles in Directed Graphs. Linear Algebra and its Applications, 75 (1986) 27-41.

Thomassen, Carsten, The Even Cycle Problem for Planar Digraphs. J. Algorithms, 15 (1993) 61-75.

Thomassen, Carsten, The Even Cycle Problem for Directed Graphs. J. Amer. Math. Soc., 5 (1992) 217-229.

Valiant, L. G., The Complexity of Computing the Permanent. Theoretical Computer Science, 8 (1979) 189-201.

Vazirani, V. J. and Mihalis Yannakakis, Pfaffian Orientations, 0-1 Permanents, and Even Cycles in Directed Graphs. Discrete Applied Math., 25 (1989) 179-190.