scientific article - MaRDI portal

zbMATH Open0800.68617MaRDI QIDQ3138921FDOQ3138921

Publication date: 20 September 1994

Title of this publication is not available (Why is that?)

data structures linking weighted matching nearest common ancestors

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (only showing first 100 items - show all)

Finding dominators via disjoint set union
An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach
A simple algorithm for finding a maximum triangle-free \(2\)-matching in subcubic graphs
Approximation algorithms for maximum dispersion
Fast algorithms for the undirected negative cost cycle detection problem
Euclidean maximum matchings in the plane -- local to global
Improved Algorithms for Detecting Negative Cost Cycles in Undirected Graphs
Mix and match: a strategyproof mechanism for multi-hospital kidney exchange
Approximation algorithms for multiple terminal, Hamiltonian path problems
Computing convex quadrangulations
Cycle bases in graphs characterization, algorithms, complexity, and applications
Succinct indices for path minimum, with applications
Title not available (Why is that?)
Parallel static and dynamic multi‐constraint graph partitioning
Weighted matching in the semi-streaming model
Fast incremental planarity testing
New common ancestor problems in trees and directed acyclic graphs
The balanced maximally diverse grouping problem with attribute values
1.5-Approximation algorithm for weighted maximum routing and wavelength assignment on rings
Minimum entropy coloring
Paths and trails in edge-colored graphs
On vertex independence number of uniform hypergraphs
Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem
Optimal on-line decremental connectivity in trees
Partitioning planar graphs: a fast combinatorial approach for max-cut
Incremental assignment problem
Approximate Max \(k\)-Cut with subgraph guarantee
Parallel approximation algorithms for maximum weighted matching in general graphs
Parameterized and approximation algorithms for finding two disjoint matchings
A simple approximation algorithm for the weighted matching problem
Gallai-Edmonds decomposition as a pruning technique
Algorithms for four variants of the exact satisfiability problem
Fast and Simple Algorithms for Weighted Perfect Matching
Priority matchings revisited
Title not available (Why is that?)
A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
Matching and weighted \(P_2\)-packing: algorithms and kernels
A simple reduction from maximum weight matching to maximum cardinality matching
On contrasting vertex contraction with relaxation-based approaches for negative cost cycle detection
Scheduling arc shut downs in a network to maximize flow over time with a bounded number of jobs per time period
Algorithms for solving the symmetry number problem on trees
An Optimal Algorithm for Plane Matchings in Multipartite Geometric Graphs
Lexicographic bottleneck combinatorial problems
Quantum algorithms for matching problems
Blossom V: A new implementation of a minimum cost perfect matching algorithm
A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
Weighted well-covered claw-free graphs
A model for minimizing active processor time
Computing the bipartite edge frustration of fullerene graphs
A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
Weighted matching as a generic pruning technique applied to optimization constraints
Title not available (Why is that?)
Minimum weighted clique cover on claw‐free perfect graphs
A new variant of a vehicle routing problem: Lower and upper bounds
Linear-Time Approximation for Maximum Weight Matching
Undirected postman problems with zigzagging option: a cutting-plane approach
Maintenance of 2- and 3-edge-connected components of graphs. I
The traveling salesman problem on cubic and subcubic graphs
An optimal algorithm for plane matchings in multipartite geometric graphs
Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems
Maintenance of triconnected components of graphs
Network-Based Vertex Dissolution
A fast algorithm for minimum weight odd circuits and cuts in planar graphs
Computing solutions for matching games
The density maximization problem in graphs
Properly Coloured Cycles and Paths: Results and Open Problems
Age-based preferences in paired kidney exchange
Paths and Trails in Edge-Colored Graphs
Optimal pointer algorithms for finding nearest common ancestors in dynamic trees
Linear-time parameterized algorithms with limited local resources
A reduction algorithm for the weighted stable set problem in claw-free graphs
Node-Balancing by Edge-Increments
On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
Paths and trails in edge-colored weighted graphs
Clustering in Hypergraphs to Minimize Average Edge Service Time
THE MAXIMUM WEIGHT PERFECT MATCHING PROBLEM FOR COMPLETE WEIGHTED GRAPHS IS IN PC∗†
On residual approximation in solution extension problems
Parallel dynamic lowest common ancestors
Randomized parameterized algorithms for the kidney exchange problem
The Level-Ancestor problem on pure pointer machines
An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs
Shortest odd paths in undirected graphs with conservative weight functions
A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints
On matchings, T‐joins, and arc routing in road networks
The difficulty of beating the Taxman
Good \(r\)-divisions imply optimal amortized decremental biconnectivity
An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem
A 3/2-approximation for big two-bar charts packing
Classes of linear programs solvable by coordinate-wise minimization
On the parametrized complexity of Read-once refutations in UTVPI+ constraint systems
A Hybrid Approach to Fast Indirect Quadrilateral Mesh Generation
Title not available (Why is that?)
Euclidean maximum matchings in the plane -- local to global
A genetic-based framework for solving (multi-criteria) weighted matching problems.
Dealing with several parameterized problems by random methods
Minimum weight euclidean matching and weighted relative neighborhood graphs
Matchings with lower quotas: algorithms and complexity
Path Minima in Incremental Unrooted Trees
On the Power of Tree-Depth for Fully Polynomial FPT Algorithms

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3138921)