The complexity of regular subgraph recognition

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

zbMATH Keywords

NP-completeregular subgraph recognition

Mathematics Subject Classification ID

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

• Graph factors
• Three‐regular subgraphs of four‐regular graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item