Network flow and 2-satisfiability
From MaRDI portal
Publication:1317481
DOI10.1007/BF01240738zbMath0795.68097WikidataQ56288400 ScholiaQ56288400MaRDI QIDQ1317481
Publication date: 11 September 1994
Published in: Algorithmica (Search for Journal in Brave)
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)
Related Items (22)
A compact representation for minimizers of \(k\)-submodular functions ⋮ Stable Marriage and Roommates Problems with Restricted Edges: Complexity and Approximability ⋮ Quasi-Popular Matchings, Optimality, and Extended Formulations ⋮ Optimizing a generalized Gini index in stable marriage problems: NP-hardness, approximation and a polynomial time special case ⋮ Computing relaxations for the three-dimensional stable matching problem with cyclic preferences ⋮ The complete set of minimal simple graphs that support unsatisfiable 2-CNFs ⋮ An artificial neural network satisfiability tester ⋮ The minimum spanning tree problem with conflict constraints and its variations ⋮ The stable roommates problem with short lists ⋮ Stable marriage and roommates problems with restricted edges: complexity and approximability ⋮ Argumentation frameworks as constraint satisfaction problems ⋮ Unnamed Item ⋮ New and simple algorithms for stable flow problems ⋮ Efficient algorithms for generalized stable marriage and roommates problems ⋮ The stable marriage problem with master preference lists ⋮ Popular edges and dominant matchings ⋮ The Stable Roommates Problem with Short Lists ⋮ Compact linear programs for 2SAT ⋮ A Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract) ⋮ A collection of constraint programming models for the three-dimensional stable matching problem with cyclic preferences ⋮ Popularity, Mixed Matchings, and Self-Duality ⋮ Understanding Popular Matchings via Stable Matchings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parametric stable marriage and minimum cuts
- Equivalent approximation algorithms for node cover
- A bounded approximation for the minimum cost 2-sat problem
- On likely solutions of a stable marriage problem
- Every finite distributive lattice is a set of stable matchings for a small stable marriage instance
- A data structure for dynamic trees
- A decomposition theorem for partially ordered sets
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- Finding Minimum-Cost Circulations by Successive Approximation
- Performance analysis of voting strategies for a fly-by-wire system of a fighter aircraft
- The Complexity of Counting Stable Marriages
- Three Fast Algorithms for Four Problems in Stable Marriage
- The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments
- Improved Time Bounds for the Maximum Flow Problem
- A linear-time approximation algorithm for the weighted vertex cover problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Vertex packings: Structural properties and algorithms
- On the Complexity of Timetable and Multicommodity Flow Problems
- Depth-First Search and Linear Graph Algorithms
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- College Admissions and the Stability of Marriage
This page was built for publication: Network flow and 2-satisfiability
