Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem (Q1185245): Difference between revisions

@@ Property / full work available at URL @@
+https://doi.org/10.1016/0022-0000(92)90005-4
+Normal rank
@@ Property / OpenAlex ID @@
+W1964011448
@@ Property / OpenAlex ID: W1964011448 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3852212
@@ Property / cites work: Q3852212 / rank @@
+Normal rank
@@ Property / cites work @@
+Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
+Normal rank
@@ Property / cites work @@
+A taxonomy of problems with fast parallel algorithms
+Normal rank
@@ Property / cites work @@
+Q3684121
@@ Property / cites work: Q3684121 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3731028
@@ Property / cites work: Q3731028 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4385522
@@ Property / cites work: Q4385522 / rank @@
+Normal rank
@@ Property / cites work @@
+Subtree isomorphism is NC reducible to bipartite perfect matching
+Normal rank
@@ Property / cites work @@
+Q3732972
@@ Property / cites work: Q3732972 / rank @@
+Normal rank
@@ Property / cites work @@
+A fast parallel algorithm for routing in permutation networks
+Normal rank
@@ Property / cites work @@
+Matching theory
@@ Property / cites work: Matching theory / rank @@
+Normal rank
@@ Property / cites work @@
+Matching is as easy as matrix inversion
@@ Property / cites work: Matching is as easy as matrix inversion / rank @@
+Normal rank