Complexity of finding maximum regular induced subgraphs with prescribed degree

DOI10.1016/j.tcs.2014.07.008zbMath1368.05143OpenAlexW3004503647MaRDI QIDQ401302

Yuichi Asahiro, Hiroshi Eto, Eiji Miyano, Takehiro Ito

Publication date: 26 August 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.07.008

zbMATH Keywords

bipartite graphgraph algorithmtreewidthchordal graphplanar graphinapproximabilityregular induced subgraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (3)

Reconfiguration of regular induced subgraphs ⋮ Computations by fly-automata beyond monadic second-order logic ⋮ Bounds for regular induced subgraphs of strongly regular graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improving an upper bound on the size of \(k\)-regular induced subgraphs
• Maximum regular induced subgraphs in \(2P_3\)-free graphs
• Approximability results for the maximum and minimum maximal induced matching problems
• Parameterized complexity of finding regular induced subgraphs
• Induced matchings
• Deciding whether a planar graph has a cubic subgraph is NP-complete
• On locating cubic subgraphs in bounded-degree connected bipartite graphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Algorithmic meta-theorems for restrictions of treewidth
• Finding regular subgraphs in both arbitrary and planar graphs
• Maximum \(k\)-regular induced subgraphs
• Tree decompositions of graphs: saving memory in dynamic programming
• Complexity of Finding Maximum Regular Induced Subgraphs with Prescribed Degree
• Strong lower bounds on the approximability of some NPO PB-complete maximization problems
• Graph Classes: A Survey
• The approximation of maximum subgraph problems
• Maximum $r$-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Complexity of finding maximum regular induced subgraphs with prescribed degree