scientific article
From MaRDI portal
zbMath0703.68046MaRDI QIDQ3995616
Robert W. Irving, Dan Gusfield
Publication date: 23 January 1993
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Parallel algorithms in computer science (68W10) Research exposition (monographs, survey articles) pertaining to computer science (68-02)
Related Items
The structure of stable marriage with indifference, Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchings, A coloring property for stable allocations, Stable matchings and linear inequalities, Characterization of super-stable matchings, The complexity of the certification of properties of stable marriage, On-line algorithms for weighted bipartite matching and stable marriages, Modelling practical placement of trainee teachers to schools, Hardness results on the man-exchange stable marriage problem with short preference lists, On random exchange-stable matchings, Improved algorithmic results for unsplittable stable allocation problems, The stable fixtures problem with payments, A maximum \(b\)-matching problem arising from median location models with applications to the roommates problem, Analysis of stochastic matching markets, Potential-partnership networks and the dynamical structure of monogamous populations, Stochastic stability for roommate markets, A one-shot deviation principle for stability in matching problems, Improved approximation algorithms for two variants of the stable marriage problem with ties, Friend of my friend: network formation with two-hop benefit, Core of coalition formation games and fixed-point methods, ``Almost stable matchings in the roommates problem with bounded preference lists, A deferred acceptance algorithm with contracts, Reconstructing edge-disjoint paths., The complexity of approximately counting stable roommate assignments, The presence of lattice theory in discrete problems of mathematical social sciences. Why., The complexity of approximately counting stable matchings, Parameterized algorithms for stable matching with ties and incomplete lists, Dynamics in matching and coalition formation games with structural constraints, Bounded unpopularity matchings, Improved approximation bounds for the student-project allocation problem with preferences over projects, A maximum stable matching for the roommates problem, The stable marriage problem with restricted pairs., Approximability results for stable marriage problems with ties., Two algorithms for the student-project allocation problem, An algorithm to compute the full set of many-to-many stable matchings., A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem, A unified approach to finding good stable matchings in the hospitals/residents setting, Singleton core in many-to-one matching problems, Antimatroids induced by matchings, On the complexity of distributed stable matching with small messages, Handling preferences in student-project allocation, The stable roommates problem with short lists, A characterization of graphs that ensure the existence of stable matchings, The existence of a unique core partition in coalition formation games, Improving man-optimal stable matchings by minimum change of preference lists, Maximum locally stable matchings, Linear time local approximation algorithm for maximum stable marriage, Local search approaches in stable matching problems, Stability, optimality and manipulation in matching problems with weighted preferences, Overlays with preferences: distributed, adaptive approximation algorithms for matching with preference lists, Stability and strategy-proofness for college admissions with an eligibility criterion, Mathematical models for stable matching problems with ties and incomplete lists, A fast algorithm for the generalized parametric minimum cut problem and applications, Characterization of stable matchings as extreme points of a polytope, Stable marriage with general preferences, A bounded approximation for the minimum cost 2-sat problem, A computational approach to the multi-period many-to-one matching with ties, Stable marriage and roommates problems with restricted edges: complexity and approximability, Fractional solutions for capacitated NTU-games, with applications to stable matchings, The lattice of envy-free matchings, Matching with indifferences: a comparison of algorithms in the context of course allocation, A new fixed point approach for stable networks and stable marriages, Complexity of the sex-equal stable marriage problem, Sex-equal stable matchings: complexity and exact algorithms, A 25/17-approximation algorithm for the stable marriage problem with one-sided ties, Rotations in the stable \(b\)-matching problem, Size versus stability in the marriage problem, Optimal popular matchings, Stable matchings in three-sided systems with cyclic preferences, Popular mixed matchings, Keeping partners together: Algorithmic results for the hospitals/residents problem with couples, Geometric stable roommates, Sexually transmitted infections and the marriage problem, Smith and Rawls share a room: stability and medians, Unravelling in two-sided matching markets and similarity of preferences, The college admissions problem with lower and common quotas, An improved approximation lower bound for finding almost stable maximum matchings, Stable matching games: manipulation via subgraph isomorphism, Efficient algorithms for generalized stable marriage and roommates problems, Student-project allocation with preferences over projects, The stable marriage problem with master preference lists, Popular edges and dominant matchings, Stable matching problems with exchange restrictions, Efficient algorithms and methods to solve dynamic MINs stability problem using stable matching with complete ties, Arbitrated matching: Formulation and protocol, A neural network approach to solve the stable matching problem, Residence exchange wanted: A stable residence exchange problem, Stable marriage with ties and bounded length preference lists, Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems, Optimizing the marriage market: an application of the linear assignment model, A sublinear parallel algorithm for stable matching, On a cutting plane heuristic for the stable roommates problem and its applications, On the uniqueness of stable marriage matchings, ``Timing is everything and marital bliss, Stable marriage and indifference, A faster parametric minimum-cut algorithm, Network flow and 2-satisfiability, A polynomial-time algorithm for the bistable roommates problem, Hard variants of stable marriage., The hospitals/residents problem with lower quotas, Strongly Stable and Maximum Weakly Stable Noncrossing Matchings, On the lattice structure of the set of stable matchings for a many-to-one model∗, COALITION FORMATION GAMES: A SURVEY, Peptide Computers, Maintaining Near-Popular Matchings, Stable Marriage and Roommates Problems with Restricted Edges: Complexity and Approximability, SOME ORDER DUALITIES IN LOGIC, GAMES AND CHOICES, Unnamed Item, The Price of Matching with Metric Preferences, Combining mutual information and stable matching strategy for dynamic evolutionary multi-objective optimization, Testing substitutability of weak preferences, On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization), Stable matchings and stable partitions∗, On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm, Unnamed Item, Finding a Level Ideal of a Poset, An upper bound for the solvability probability of a random stable roommates instance, Fast Detection of Stable and Count Predicates in Parallel Computations, Stability against robust deviations in the roommate problem, Unnamed Item, Descending the stable matching lattice: how many strategic agents are required to turn pessimality to optimality?, Legal Assignments and Fast EADAM with Consent via Classic Theory of Stable Matchings, Profile-Based Optimal Matchings in the Student/Project Allocation Problem, Disjoint stable matchings in linear time, The graphs of stably matchable pairs, Cycles to compute the full set of many-to-many stable matchings, Review of the theory of stable matchings and contract systems, Stable and extremely unequal, Marriage and Roommate, Counterexamples of small size for three-sided stable matching with cyclic preferences, Computing relaxations for the three-dimensional stable matching problem with cyclic preferences, Balancing stability and efficiency in team formation as a generalized roommate problem, Telecommunications network design: Technology impacts and future directions, The Stable Roommates Problem with Choice Functions, Recognizing when a preference system is close to admitting a master list, Computing lexicographically safe Nash equilibria in finite two-person games with tight game forms given by oracles, Recognizing when a preference system is close to admitting a master list, Refined computational complexities of hospitals/residents problem with regional caps, Stable allocations and partially ordered sets, Algorithms and complexity of strongly stable non-crossing matchings, Envy-freeness and relaxed stability for lower-quotas: a parameterized perspective, Unnamed Item, Bounded Unpopularity Matchings, Network Essence: PageRank Completion and Centrality-Conforming Markov Chains, Locally Stable Marriage with Strict Preferences, Unnamed Item, Multi-agent reinforcement learning for decentralized stable matching, A counterexample of size 20 for the problem of finding a 3-dimensional stable matching with cyclic preferences, On coloring problems with local constraints, Unnamed Item, A General Framework for Stable Roommates Problems using Answer Set Programming, How hard is it to satisfy (almost) all roommates, Stable roommates problem with random preferences, Small random instances of the stable roommates problem, Cooperative Games (Von Neumann-Morgenstern Stable Sets), On the Likely Number of Solutions for the Stable Marriage Problem, Bribery and Control in Stable Marriage, Improved Approximation Bounds for the Student-Project Allocation Problem with Preferences over Projects, Popular Matchings in the Stable Marriage Problem, Center Stable Matchings and Centers of Cover Graphs of Distributive Lattices, Local Matching Dynamics in Social Networks, Beauty and distance in the stable marriage problem, Sex-oriented stable matchings of the marriage problem with correlated and incomplete information, From Marriages to Coalitions: A Soft CSP Approach, Unnamed Item, Size Versus Stability in the Marriage Problem, New and simple algorithms for stable flow problems, On the complexity of exchange-stable roommates, Unnamed Item, An efficient implementation of the Gale and Shapley “propose-and-reject” algorithm, The Generalized Median Stable Matchings: Finding Them Is Not That Easy, Balanced stable marriage: how close is close enough?, Affinely representable lattices, stable matchings, and choice functions, A Matroid Approach to Stable Matchings with Lower Quotas, Affinely representable lattices, stable matchings, and choice functions, Random stable matchings, Finding All Stable Pairs and Solutions to the Many-to-Many Stable Matching Problem, On Likely Solutions of the Stable Matching Problem with Unequal Numbers of Men and Women, Stable Matching with Uncertain Linear Preferences, The Stable Roommates Problem with Short Lists, On the complexity of stable fractional hypergraph matching, The Perfect Matching Reconfiguration Problem, Algorithmic Aspects of Equilibria of Stable Marriage Model with Complete Preference Lists, On the Stable Matchings That Can Be Reached When the Agents Go Marching in One By One, EMPLOYMENT BY LOTTO REVISITED, Unnamed Item, Unnamed Item, Unnamed Item, On Vertices and Facets of Combinatorial 2-Level Polytopes, Unnamed Item, Polyhedral Aspects of Stable Marriage, A New Approach to the Pareto Stable Matching Problem, Popularity, Mixed Matchings, and Self-Duality, MATCHING WITH COUPLES: A MULTIDISCIPLINARY SURVEY, On the Lattice Structure of Stable Allocations in a Two-Sided Discrete-Concave Market, Unnamed Item, Unnamed Item, How Good Are Popular Matchings, Understanding Popular Matchings via Stable Matchings, Refined computational complexities of hospitals/residents problem with regional caps, Matching games with partial information, Randomized approximation of the stable marriage problem, A solution to matching with preferences over colleagues, NP-completeness in hedonic games, Polynomial time algorithm for an optimal stable assignment with multiple partners, On the integration of Shapley-Scarf markets, Stable matching of student-groups to dormitories, Two-sided matching markets with strongly correlated preferences, How do I marry thee? Let me count the ways, A new solution concept for the roommate problem: \(\mathcal{Q}\)-stable matchings, The cycle roommates problem: a hard case of kidney exchange, Blockers and antiblockers of stable matchings, The stable fixtures problem -- a many-to-many extension of stable roommates, The core of housing markets from an agent's perspective: Is it worth sprucing up your home?, Paths to marriage stability, Popularity in the generalized hospital residents setting, Canonical monotone decompositions of fractional stable matchings, A local interaction dynamic for the matching problem, Stable matchings with couples, From model checking to equilibrium checking: reactive modules for rational verification, Stable matching with network externalities, Stable matchings and linear programming, An exploration in school formation: income vs. ability, Preference profiles determining the proposals in the Gale-Shapley algorithm for stable matching problems, Optimizing a generalized Gini index in stable marriage problems: NP-hardness, approximation and a polynomial time special case, Two problems in max-size popular matchings, Subquadratic algorithms for succinct stable matching, The kidney exchange problem: how hard is it to find a donor?, Complexity study for the robust stable marriage problem, Robust and approximately stable marriages under partial information, The core of roommate problems: size and rank-fairness within matched pairs, Agreeable sets with matroidal constraints, Jointly stable matchings, On random stable matchings: cyclic ones with strict preferences and two-sided ones with partially ordered preferences, Contribution games in networks, Solving hard stable matching problems involving groups of similar agents, Absorbing sets in roommate problems, The integral stable allocation problem on graphs, Equilibria under deferred acceptance: dropping strategies, filled positions, and welfare, Sisterhood in the Gale-Shapley matching algorithm, Entering classes in the college admissions model, The roommates problem revisited, Understanding the generalized median stable matchings, The stable roommates problem with choice functions, Three-sided stable matchings with cyclic preferences, An efficient algorithm for batch stability testing, Parameterized complexity and local search approaches for the stable marriage problem with ties, Housing markets through graphs, Almost stable matchings by truncating the Gale-Shapley algorithm, Circular stable matching and 3-way kidney transplant, Cheating strategies for the Gale-Shapley algorithm with complete preference lists, A polynomial-time algorithm to find von Neumann-Morgenstern stable matchings in marriage games, Faster algorithms for stable allocation problems, Edge-coloring almost bipartite multigraphs, What price stability? Social welfare in matching markets, Subjective homophily and the fixtures problem, One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences, Bistable versions of the marriages and roommates problems, The communication requirements of social choice rules and supporting budget sets, The stable marriage problem: an interdisciplinary review from the physicist's perspective, Strongly stable and maximum weakly stable noncrossing matchings, Stable fractional matchings, Characterizations of the optimal stable allocation mechanism, Envy-free matchings with lower quotas, On the stable \(b\)-matching problem in multigraphs, Matching with externalities: the role of prudence and social connectedness in stability, Stable secretaries, On random stable partitions, Instability of matchings in decentralized markets with various preference structures, Deferred acceptance algorithms: history, theory, practice, and open questions, A Davidson college multi-objective assignment problem: a case study, A compact representation for modular semilattices and its applications, Median stable matching for college admissions, A general two-sided matching market with discrete concave utility functions, Optimization problems involving collections of dependent objects, The roommate problem with externalities, Improving solution times for stable matching problems through preprocessing, A stable marriage requires communication, A necessary and sufficient condition for stable matching rules to be strategy-proof, Unpopularity factor in the marriage and roommates problems, Transformation from arbitrary matchings to stable matchings, A generalization of the stable matching problem, Courtship and linear programming, The set of super-stable marriages forms a distributive lattice, The diameter of the stable marriage polytope: bounding from below, A characterization of strongly stable fractional matchings, (Un)stable matchings with blocking costs, Coalitional permutation manipulations in the Gale-Shapley algorithm, Stable matchings with covering constraints: a complete computational trichotomy, Stable matching with uncertain linear preferences, Stable partitions with \(\mathcal W\)-preferences, The stable crews problem, Stable matching with uncertain pairwise preferences, A collection of constraint programming models for the three-dimensional stable matching problem with cyclic preferences, Paths to stable allocations, A real polynomial for bipartite graph minimum weight perfect matchings, The exchange-stable marriage problem, Binary operations and lattice structure for a model of matching with contracts, Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters, Bipartite choices
