Network flow and 2-satisfiability
From MaRDI portal
Publication:1317481
DOI10.1007/BF01240738zbMATH Open0795.68097WikidataQ56288400 ScholiaQ56288400MaRDI QIDQ1317481FDOQ1317481
Authors: Tomás Feder 
Publication date: 11 September 1994
Published in: Algorithmica (Search for Journal in Brave)
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Depth-First Search and Linear Graph Algorithms
- A data structure for dynamic trees
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- Title not available (Why is that?)
- The Complexity of Counting Stable Marriages
- Three Fast Algorithms for Four Problems in Stable Marriage
- Title not available (Why is that?)
- Title not available (Why is that?)
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- College Admissions and the Stability of Marriage
- Finding Minimum-Cost Circulations by Successive Approximation
- A linear-time approximation algorithm for the weighted vertex cover problem
- Vertex packings: Structural properties and algorithms
- On the Complexity of Timetable and Multicommodity Flow Problems
- A decomposition theorem for partially ordered sets
- Title not available (Why is that?)
- A bounded approximation for the minimum cost 2-sat problem
- The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments
- On likely solutions of a stable marriage problem
- Improved Time Bounds for the Maximum Flow Problem
- Every finite distributive lattice is a set of stable matchings for a small stable marriage instance
- Parametric stable marriage and minimum cuts
- Equivalent approximation algorithms for node cover
- Performance analysis of voting strategies for a fly-by-wire system of a fighter aircraft
Cited In (29)
- The stable roommates problem with short lists
- Understanding popular matchings via stable matchings
- Title not available (Why is that?)
- The stable marriage problem with master preference lists
- A compact representation for minimizers of \(k\)-submodular functions
- Popularity, Mixed Matchings, and Self-Duality
- Title not available (Why is that?)
- Computing relaxations for the three-dimensional stable matching problem with cyclic preferences
- Adapting stable matchings to forced and forbidden pairs
- Stable marriage and roommates problems with restricted edges: complexity and approximability
- An artificial neural network satisfiability tester
- The Stable Roommates Problem with Short Lists
- A Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract)
- Quasi-popular matchings, optimality, and extended formulations
- Maximum matchings and popularity
- The binary network flow problem is logspace complete for P
- The minimum spanning tree problem with conflict constraints and its variations
- Title not available (Why is that?)
- The complete set of minimal simple graphs that support unsatisfiable 2-CNFs
- A collection of constraint programming models for the three-dimensional stable matching problem with cyclic preferences
- Optimizing a generalized Gini index in stable marriage problems: NP-hardness, approximation and a polynomial time special case
- Argumentation frameworks as constraint satisfaction problems
- Efficient algorithms for generalized stable marriage and roommates problems
- Finite Termination of “Augmenting Path” Algorithms in the Presence of Irrational Problem Data
- Compact linear programs for 2SAT
- Title not available (Why is that?)
- Stable marriage and roommates problems with restricted edges: complexity and approximability
- Formalizing network flow algorithms: a refinement approach in Isabelle/HOL
- Title not available (Why is that?)
This page was built for publication: Network flow and 2-satisfiability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1317481)
