Complexity of finding maximum regular induced subgraphs with prescribed degree
treewidthbipartite graphgraph algorithminapproximabilityplanar graphchordal graphregular induced subgraph
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)
- Complexity of finding maximum regular induced subgraphs with prescribed degree
- Parameterized complexity of finding regular induced subgraphs
- Maximum \(k\)-regular induced subgraphs
- Maximum \(r\)-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds
- The complexity of regular subgraph recognition
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 554762 (Why is no real title available?)
- scientific article; zbMATH DE number 1142315 (Why is no real title available?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Algorithmic meta-theorems for restrictions of treewidth
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Approximability results for the maximum and minimum maximal induced matching problems
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Complexity of finding maximum regular induced subgraphs with prescribed degree
- Deciding whether a planar graph has a cubic subgraph is NP-complete
- Finding regular subgraphs in both arbitrary and planar graphs
- Graph Classes: A Survey
- Improving an upper bound on the size of \(k\)-regular induced subgraphs
- Induced matchings
- Maximum \(k\)-regular induced subgraphs
- Maximum \(r\)-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds
- Maximum regular induced subgraphs in \(2P_3\)-free graphs
- On locating cubic subgraphs in bounded-degree connected bipartite graphs
- Parameterized complexity of finding regular induced subgraphs
- Strong lower bounds on the approximability of some NPO PB-complete maximization problems
- The approximation of maximum subgraph problems
- Tree decompositions of graphs: saving memory in dynamic programming
- Maximum locally irregular induced subgraphs via minimum irregulators
- Maximum regular induced subgraphs in \(2P_3\)-free graphs
- Fast Exponential Algorithms for Maximum r-Regular Induced Subgraph Problems
- Parameterized complexity of finding regular induced subgraphs
- Bounds for regular induced subgraphs of strongly regular graphs
- Computations by fly-automata beyond monadic second-order logic
- Complexity of finding maximum regular induced subgraphs with prescribed degree
- Polynomial time algorithms for two classes of subgraph problem
- Reconfiguration of regular induced subgraphs
- A note on the complexity of finding regular subgraphs
- Maximum \(r\)-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds
- On the complexity of deciding whether the regular number is at most two
- Algorithmic complexity of weakly semiregular partitioning and the representation number
- On the complexity of the identifiable subgraph problem
- Sparse regular induced subgraphs in \(2P_3\)-free graphs
This page was built for publication: Complexity of finding maximum regular induced subgraphs with prescribed degree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q401302)
