scientific article

Publication date: 20 September 1994

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

data structures linking weighted matching nearest common ancestors

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

Related Items (only showing first 100 items - show all)

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

This page was built for publication: