Polynomial time algorithms for two classes of subgraph problem

DOI10.1051/RO:2008015MaRDI QIDQ3598037zbMATH OpenOpenAlexFDO

Authors Sriraman Sridharan

Publication date 29 January 2009

Published in RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/105403, https://semanticscholar.org/paper/99f413dbcf94d29c7f49ac40c2bc5fcfba93ddeb

zbMATH Keywords

graphNP-completeperfect matchingregular graphpolynomial time algorithmstar

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The complexity of regular subgraph recognition
• Finding regular subgraphs in both arbitrary and planar graphs
• Subgraphs of 4-regular planar graphs
• An efficient algorithm for cyclic edge connectivity of regular graphs.
• Complexity of finding maximum regular induced subgraphs with prescribed degree

Cites work

• scientific article; zbMATH DE number 4150223 (Why is no real title available?)
• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• scientific article; zbMATH DE number 3492724 (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?)
• scientific article; zbMATH DE number 844701 (Why is no real title available?)
• Graph theory
• Paths, Trees, and Flowers
• The Factorization of Linear Graphs
• Three‐regular subgraphs of four‐regular graphs

Cited in

(4)

• Polynomial-Time Algorithms for Subgraph Isomorphism in Small Graph Classes of Perfect Graphs
• Subexponential parameterized algorithms for graphs of polynomial growth
• Subgraphs of 4-regular planar graphs
• Characterizations of Natural Submodular Graphs: A Polynomially Solvable Class of the TSP

This page was built for publication: Polynomial time algorithms for two classes of subgraph problem

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