A note on the complexity of finding regular subgraphs

DOI10.1016/0012-365X(84)90113-4MaRDI QIDQ1059641zbMATH OpenFDO

Authors Ján Plesník

Publication date 1984

Published in Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-completenessdetecting regular subgraphs in a given graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph theory (05C99)

Recommendations

• scientific article; zbMATH DE number 844701
• The complexity of regular subgraph recognition
• Parameterized complexity of finding regular induced subgraphs
• On the complexity of some subgraph problems
• Note on regular subgraphs
• scientific article; zbMATH DE number 3910446
• Finding regular subgraphs in both arbitrary and planar graphs
• Addendum to: The complexity of regular subgraph recognition
• Complexity of finding maximum regular induced subgraphs with prescribed degree
• Complexity of finding maximum regular induced subgraphs with prescribed degree

Cites work

• scientific article; zbMATH DE number 3743298 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3625415 (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 theory
• On a problem of K. Zarankiewicz
• On the berge—sauer conjecture
• Parallel concepts in graph theory
• Three‐regular subgraphs of four‐regular graphs

Cited in

(13)

• The complexity of regular subgraph recognition
• On the complexity of nucleolus computation for bipartite \(b\)-matching games
• Parameterized Graph Editing with Chosen Vertex Degrees
• Graph theory (algorithmic, algebraic, and metric problems)
• Editing graphs to satisfy degree constraints: a parameterized approach
• The stable fixtures problem with payments
• scientific article; zbMATH DE number 930115 (Why is no real title available?)
• 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
• Parameterized complexity of finding small degree-constrained subgraphs
• Graph editing problems with extended regularity constraints

This page was built for publication: A note on the complexity of finding regular subgraphs

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