A new fixed point approach for stable networks and stable marriages
From MaRDI portal
Publication:1201153
DOI10.1016/0022-0000(92)90048-NzbMath0772.68052OpenAlexW2952126919MaRDI QIDQ1201153
Publication date: 17 January 1993
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(92)90048-n
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (35)
Complexity of fixed point counting problems in Boolean networks ⋮ Stable Marriage and Roommates Problems with Restricted Edges: Complexity and Approximability ⋮ The Price of Matching with Metric Preferences ⋮ On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization) ⋮ Quasi-Popular Matchings, Optimality, and Extended Formulations ⋮ Stable matchings and linear programming ⋮ Review of the theory of stable matchings and contract systems ⋮ Computing relaxations for the three-dimensional stable matching problem with cyclic preferences ⋮ The Stable Roommates Problem with Choice Functions ⋮ The stable roommates problem with choice functions ⋮ Approximability results for stable marriage problems with ties. ⋮ A unified approach to finding good stable matchings in the hospitals/residents setting ⋮ A General Framework for Stable Roommates Problems using Answer Set Programming ⋮ Stable schedule matchings ⋮ The stable roommates problem with short lists ⋮ How hard is it to satisfy (almost) all roommates ⋮ The stable marriage problem: an interdisciplinary review from the physicist's perspective ⋮ Using maximal independent sets to solve problems in parallel ⋮ Stable fractional matchings ⋮ Stable marriage and roommates problems with restricted edges: complexity and approximability ⋮ Rotations in the stable \(b\)-matching problem ⋮ Unnamed Item ⋮ New and simple algorithms for stable flow problems ⋮ Efficient algorithms for generalized stable marriage and roommates problems ⋮ Popular edges and dominant matchings ⋮ Efficient algorithms and methods to solve dynamic MINs stability problem using stable matching with complete ties ⋮ The Stable Roommates Problem with Short Lists ⋮ Compact linear programs for 2SAT ⋮ The complexity of the comparator circuit value problem ⋮ A collection of constraint programming models for the three-dimensional stable matching problem with cyclic preferences ⋮ On a cutting plane heuristic for the stable roommates problem and its applications ⋮ Popularity, Mixed Matchings, and Self-Duality ⋮ Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters ⋮ Hard variants of stable marriage. ⋮ Understanding Popular Matchings via Stable Matchings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A dynamic location problem for graphs
- Retract rigid Cartesian products of graphs
- Equivalent approximation algorithms for node cover
- A fixed cube theorem for median graphs
- On connectivity of triangulations of manifolds
- A bounded approximation for the minimum cost 2-sat problem
- Every finite distributive lattice is a set of stable matchings for a small stable marriage instance
- A decomposition theorem for partially ordered sets
- Absolute Retracts and Varieties of Reflexive Graphs
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- Retracts of hypercubes
- Finding Minimum-Cost Circulations by Successive Approximation
- On Isometric Embeddings of Graphs
- An efficient algorithm for the “stable roommates” problem
- 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
- n‐cubes and median graphs
- A linear-time approximation algorithm for the weighted vertex cover problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Product graph representations
- Vertex packings: Structural properties and algorithms
- A New Approach to Stable Matching Problems
- Depth-First Search and Linear Graph Algorithms
- College Admissions and the Stability of Marriage
This page was built for publication: A new fixed point approach for stable networks and stable marriages
