Complexity of finding maximum regular induced subgraphs with prescribed degree
DOI10.1016/J.TCS.2014.07.008zbMATH Open1368.05143OpenAlexW3004503647MaRDI QIDQ401302FDOQ401302
Authors: Yuichi Asahiro, Hiroshi Eto, Takehiro Ito, Eiji Miyano 
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
Recommendations
- 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
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)
Cites Work
- Title not available (Why is that?)
- Graph Classes: A Survey
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Parameterized complexity of finding regular induced subgraphs
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Algorithmic meta-theorems for restrictions of treewidth
- Maximum \(k\)-regular induced subgraphs
- Maximum regular induced subgraphs in \(2P_3\)-free graphs
- Title not available (Why is that?)
- Induced matchings
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Strong lower bounds on the approximability of some NPO PB-complete maximization problems
- Title not available (Why is that?)
- Maximum \(r\)-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds
- Approximability results for the maximum and minimum maximal induced matching problems
- The approximation of maximum subgraph problems
- Deciding whether a planar graph has a cubic subgraph is NP-complete
- On locating cubic subgraphs in bounded-degree connected bipartite graphs
- Finding regular subgraphs in both arbitrary and planar graphs
- Tree decompositions of graphs: saving memory in dynamic programming
- Complexity of finding maximum regular induced subgraphs with prescribed degree
- Improving an upper bound on the size of \(k\)-regular induced subgraphs
Cited In (15)
- Complexity of finding maximum regular induced subgraphs with prescribed degree
- Fast Exponential Algorithms for Maximum r-Regular Induced Subgraph Problems
- Maximum regular induced subgraphs in \(2P_3\)-free graphs
- On the complexity of the identifiable subgraph problem
- Parameterized complexity of finding regular induced subgraphs
- A note on the complexity of finding regular subgraphs
- Sparse regular induced subgraphs in \(2P_3\)-free graphs
- Bounds for regular induced subgraphs of strongly regular graphs
- Reconfiguration of regular induced subgraphs
- Computations by fly-automata beyond monadic second-order logic
- On the complexity of deciding whether the regular number is at most two
- Maximum \(r\)-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds
- Maximum locally irregular induced subgraphs via minimum irregulators
- Polynomial time algorithms for two classes of subgraph problem
- Algorithmic complexity of weakly semiregular partitioning and the representation number
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)
