The complexity of restricted spanning tree problems
From MaRDI portal
Publication:3936213
DOI10.1145/322307.322309zbMath0478.68068OpenAlexW2079828065MaRDI QIDQ3936213
Mihalis Yannakakis, Christos H. Papadimitriou
Publication date: 1982
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322307.322309
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)
Related Items
Knapsack problem with objective value gaps, Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree, Heuristic and exact algorithms for the spanning tree detection problem, Decision-making based on approximate and smoothed Pareto curves, Random parallel algorithms for finding exact branchings, perfect matchings, and cycles, Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs, Exact arborescences, matchings and cycles, Solving linear equations parameterized by Hamming weight, Matching is as easy as matrix inversion, Spanning trees with minimum weighted degrees, Balanced spanning forests and trees, Isomorphic tree spanner problems, Optimizing over a slice of the bipartite matching polytope, Simple paths with exact and forbidden lengths, Approximation Methods for Multiobjective Optimization Problems: A Survey, The complexity of matching with bonds, A weighted perfect matching with constraints on weights of its parts, A \(5k\)-vertex kernel for 3-path vertex cover, The maximum number of maximum dissociation sets in trees, Integrality gaps for colorful matchings, Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle, Group control for consent rules with consecutive qualifications, Unnamed Item, On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number, Almost exact matchings, A faster FPT algorithm for 3-path vertex cover, Extremal vertex-degree function index with given order and dissociation number, On spectral extrema of graphs with given order and dissociation number, Filling crosswords is very hard, Uniformly dissociated graphs, On computing the minimum 3-path vertex cover and dissociation number of graphs, Nonlinear bipartite matching, Graphical-structure-based models for routing problems, Kernelization and Parameterized Algorithms for 3-Path Vertex Cover, Minimizing the number of late jobs on a single machine under due date uncertainty, Bi-criteria and approximation algorithms for restricted matchings, Approximating the Maximally Balanced Connected Partition Problem in graphs, A polynomial time equivalence between DNA sequencing and the exact perfect matching problem, Deterministic Algorithms for Multi-criteria TSP, Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems, On complexity of special maximum matchings constructing, Matching theory -- a sampler: From Dénes König to the present, On the difficulty of finding walks of length k, Fast geometric approximation techniques and geometric embedding problems, Intractability of approximate multi-dimensional nonlinear optimization on independence systems, Budgeted matching and budgeted matroid intersection via the gasoline puzzle, Hitting subgraphs in \(P_4\)-tidy graphs, Deterministic algorithms for multi-criteria max-TSP, The complexity of dissociation set problems in graphs, Cooperation in Multiorganization Matching, Approximation algorithms for multi-criteria traveling salesman problems, Generalized Center Problems with Outliers, Partitioning a graph into small pieces with applications to path transversal, Unnamed Item, Corrigendum to ``The complexity of cubical graphs, An algebraic Monte-Carlo algorithm for the partition adjacency matrix realization problem, The Exact Weighted Independent Set Problem in Perfect Graphs and Related Classes, General d-position sets, The \(k\)-separator problem: polyhedra, complexity and approximation results
