The complexity of regular subgraph recognition

DOI10.1016/0166-218X(90)90129-ZMaRDI QIDQ912615zbMATH OpenOpenAlexFDO

Authors F. Cheah, Derek G. 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) Graph theory (05C99) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Addendum to: The complexity of regular subgraph recognition
• On the computational complexity of ordered subgraph recognition
• A note on the complexity of finding regular subgraphs
• scientific article; zbMATH DE number 3910446
• On the complexity of the identifiable subgraph problem
• On the complexity of the identifiable subgraph problem, revisited
• On the complexity of some subgraph problems
• On the recognition complexity of some graph properties
• Parameterized complexity of finding regular induced subgraphs

Cites work

• scientific article; zbMATH DE number 3875318 (Why is no real title available?)
• scientific article; zbMATH DE number 3878359 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3807663 (Why is no real title available?)
• Graph factors
• Graph theory with applications
• Three‐regular subgraphs of four‐regular graphs

Cited in

(27)

• Complexity of finding maximum regular induced subgraphs with prescribed degree
• Approximating bounded-degree spanning trees and connected factors with leaves
• Approximation algorithms for connected graph factors of minimum weight
• Complexity of finding maximum regular induced subgraphs with prescribed degree
• On the complexity of the maximum subgraph problem
• On the complexity of some subgraph problems
• Parameterized Graph Editing with Chosen Vertex Degrees
• Spectrally degenerate graphs: hereditary case
• Approximation and exact algorithms for special cases of connected \(f\)-factors
• On the structure of trapezoid graphs
• A note on the complexity of finding regular subgraphs
• scientific article; zbMATH DE number 3910446 (Why is no real title available?)
• On NP-hard graph properties characterized by the spectrum
• Editing graphs to satisfy degree constraints: a parameterized approach
• Tight complexity bounds for FPT subgraph problems parameterized by clique-width
• The equitable dispersion problem
• Complexity of some graph-based bounds on the probability of a union of events
• Addendum to: The complexity of regular subgraph recognition
• On the complexity of deciding whether the regular number is at most two
• Graph factors and factorization: 1985--2003: a survey
• Construction of k-matchings in graph products
• On the complexity landscape of connected \(f\)-factor problems
• Polynomial time algorithms for two classes of subgraph problem
• Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
• Parameterized complexity of finding small degree-constrained subgraphs
• A linear time algorithm to compute a dominating path in an AT-free graph
• Graph editing problems with extended regularity constraints

This page was built for publication: The complexity of regular subgraph recognition

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