We give a polynomial-time algorithm for the following problem of P61ya.Given an n x n O-1 matrix, either find a matrix obtained from it by changing some of the 1's to -1's in such a way that the determinant of the new matrix equals the permanent of the old one, or determine that no such matrix exists.This is equivalent to finding Pfafiian orientations of bipartite graphs and to the even circuit problem for directed graphs.The aigorithm is based on a structural characterization of bipartite graphs that admit a Pfaffian orientation.-

Article Free Access Share on Efficiently four-coloring planar graphs Authors: Neil Robertson Department of Mathematics, The Ohio State University, Columbus, Ohio Department of Mathematics, The Ohio State University, Columbus, OhioView Profile , Daniel P. Sanders Department of Mathematics, The Ohio State University, Columbus, Ohio Department of Mathematics, The Ohio State University, Columbus, OhioView Profile , Paul Seymour Bellcore, 445 South Street, Morristown, New Jersey Bellcore, 445 South Street, Morristown, New JerseyView Profile , Robin Thomas School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia School of Mathematics, Georgia Institute of Technology, Atlanta, GeorgiaView Profile Authors Info & Claims STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of ComputingJuly 1996 Pages 571–575https://doi.org/10.1145/237814.238005Published:01 July 1996Publication History 63citation2,172DownloadsMetricsTotal Citations63Total Downloads2,172Last 12 Months487Last 6 weeks60 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF