Improving an upper bound on the size of \(k\)-regular induced subgraphs

DOI10.1007/s10878-010-9345-3zbMath1263.90117OpenAlexW2165108720MaRDI QIDQ411262

Carlos J. Luz

Publication date: 4 April 2012

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-010-9345-3

zbMATH Keywords

combinatorial optimizationgraphsindependent setsinduced matchings

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Related Items (2)

Complexity of finding maximum regular induced subgraphs with prescribed degree ⋮ The \(k\)-regular induced subgraph problem

Uses Software

• SDPT3

Cites Work

• Unnamed Item
• Geometric algorithms and combinatorial optimization
• The sandwich theorem
• An upper bound on the independence number of a graph computable in polynomial-time
• Maximum \(k\)-regular induced subgraphs
• A Redistributed Proximal Bundle Method for Nonconvex Optimization
• On the Shannon capacity of a graph
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• Maxima for Graphs and a New Proof of a Theorem of Turán
• A Convex Quadratic Characterization of the Lovász Theta Number

This page was built for publication: Improving an upper bound on the size of \(k\)-regular induced subgraphs