On locating cubic subgraphs in bounded-degree connected bipartite graphs

DOI10.1016/0012-365X(95)00324-PzbMath0873.68097OpenAlexW2023540209WikidataQ127155184 ScholiaQ127155184MaRDI QIDQ1356566

Iain A. Stewart

Publication date: 9 June 1997

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(95)00324-p

zbMATH Keywords

connected bipartite graphcubic subgraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (10)

Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width ⋮ Finding regular subgraphs in both arbitrary and planar graphs ⋮ Tight complexity bounds for FPT subgraph problems parameterized by the clique-width ⋮ Complexity of finding maximum regular induced subgraphs with prescribed degree ⋮ Editing graphs to satisfy degree constraints: a parameterized approach ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Graph editing problems with extended regularity constraints ⋮ Parameterized complexity of finding regular induced subgraphs ⋮ Parameterized Graph Editing with Chosen Vertex Degrees ⋮ Program schemes, arrays, Lindström quantifiers and zero-one laws

Cites Work

• Complete problems for monotone NP
• Deciding whether a planar graph has a cubic subgraph is NP-complete
• The NP-completeness column: an ongoing guide
• Languages that Capture Complexity Classes
• `` Strong NP-Completeness Results

This page was built for publication: On locating cubic subgraphs in bounded-degree connected bipartite graphs