Maximum \(k\)-regular induced subgraphs
From MaRDI portal
Publication:2426653
DOI10.1007/s10878-007-9045-9zbMath1149.90169OpenAlexW2119626000MaRDI QIDQ2426653
Vadim V. Lozin, Domingos Moreira Cardoso, Marcin Kaminski
Publication date: 23 April 2008
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-007-9045-9
Abstract computational complexity for mathematical programming problems (90C60) Multi-objective and goal programming (90C29) Dynamic programming (90C39)
Related Items
Induced 2-regular subgraphs in \(k\)-chordal cubic graphs ⋮ Augmenting approach for some maximum set problems ⋮ Spectral Bounds for the k-Regular Induced Subgraph Problem ⋮ Complexity of finding maximum regular induced subgraphs with prescribed degree ⋮ Improving an upper bound on the size of \(k\)-regular induced subgraphs ⋮ Parameterized complexity of finding small degree-constrained subgraphs ⋮ Editing graphs to satisfy degree constraints: a parameterized approach ⋮ Classes of intersection digraphs with good algorithmic properties ⋮ Fair domination in graphs ⋮ The complexity of uniform Nash equilibria and related regular subgraph problems ⋮ Spectral characterization of families of split graphs ⋮ Graphs with least eigenvalue \(-2\): ten years on ⋮ Induced cycles in graphs ⋮ Graph editing problems with extended regularity constraints ⋮ Maximum regular induced subgraphs in \(2P_3\)-free graphs ⋮ Approximating the maximum size of a \(k\)-regular induced subgraph by an upper bound on the co-\(k\)-plex number ⋮ Integral graphs and \((k,\tau )\)-regular sets ⋮ Spectral upper bounds for the order of a \(k\)-regular induced subgraph ⋮ The \(k\)-regular induced subgraph problem ⋮ Sparse regular induced subgraphs in \(2P_3\)-free graphs ⋮ Parameterized complexity of finding regular induced subgraphs ⋮ Spectral upper bounds on the size of k-regular induced subgraphs ⋮ An overview of \((\kappa, \tau)\)-regular sets and their applications ⋮ Bounds for regular induced subgraphs of strongly regular graphs ⋮ Moderately exponential time algorithms for the maximum induced matching problem
Cites Work
- Unnamed Item
- Unnamed Item
- Spectral results on regular graphs with \((k,\tau)\)-regular sets
- NP-completeness of some generalizations of the maximum matching problem
- Induced matchings
- Efficient edge domination problems in graphs
- Equitable bipartitions of graphs and related results
- An upper bound on the independence number of a graph computable in polynomial-time
- Graphs with least eigenvalue -2 attaining a convex quadratic upper bound for the stability number
- On the Shannon capacity of a graph
