The complexity of regular subgraph recognition
From MaRDI portal
Publication:912615
DOI10.1016/0166-218X(90)90129-ZzbMath0698.68040OpenAlexW2076040942MaRDI QIDQ912615
F. Cheah, Derek Gordon Corneil
Publication date: 1990
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(90)90129-z
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity of computation (including implicit computational complexity) (03D15) Graph theory (05C99)
Related Items
Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width, Construction of k-matchings in graph products, Approximation and Exact Algorithms for Special Cases of Connected f-Factors, Graph factors and factorization: 1985--2003: a survey, On the structure of trapezoid graphs, Tight complexity bounds for FPT subgraph problems parameterized by the clique-width, On the complexity landscape of connected \(f\)-factor problems, Parameterized complexity of finding small degree-constrained subgraphs, Editing graphs to satisfy degree constraints: a parameterized approach, Approximating bounded-degree spanning trees and connected factors with leaves, Addendum to: The complexity of regular subgraph recognition, A linear time algorithm to compute a dominating path in an AT-free graph, Approximation algorithms for connected graph factors of minimum weight, Complexity of some graph-based bounds on the probability of a union of events, Graph editing problems with extended regularity constraints, On the complexity of some subgraph problems, Spectrally degenerate graphs: hereditary case, The equitable dispersion problem, Parameterized Graph Editing with Chosen Vertex Degrees
Cites Work
