Maximum $r$-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds
From MaRDI portal
Publication:4915198
DOI10.1137/09077850XzbMath1261.05066OpenAlexW1983652976MaRDI QIDQ4915198
Saket Saurabh, Venkatesh Raman, Sushmita Gupta
Publication date: 9 April 2013
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/09077850x
exact exponential time algorithmscombinatorial upper and lower boundsmaximal \(r\)-regular subgraphs
Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal combinatorics (05D99)
Related Items
Faster exact algorithms for some terminal set problems, On the number of connected sets in bounded degree graphs, Almost Induced Matching: Linear Kernels and Parameterized Algorithms, Largest chordal and interval subgraphs faster than \(2^n\), Exact algorithms for maximum induced matching, Improved bounds for minimal feedback vertex sets in tournaments, Complexity of finding maximum regular induced subgraphs with prescribed degree, Large Induced Subgraphs via Triangulations and CMSO, Minimum number of maximal dissociation sets in trees, Perfectly matched sets in graphs: parameterized and exact computation, Parameterized algorithms and kernels for almost induced matching, Exact algorithms for minimum weighted dominating induced matching, Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs, Maximal Induced Matchings in Triangle-Free Graphs, Moderately exponential time algorithms for the maximum induced matching problem
