Maximum regular induced subgraphs in \(2P_3\)-free graphs

DOI10.1016/j.tcs.2012.06.014zbMath1252.68155MaRDI QIDQ690473

Raffaele Mosca, Vadim V. Lozin

Publication date: 27 November 2012

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

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

zbMATH Keywords

independent set; polynomial-time algorithm; clique; induced matching; regular induced subgraph; \(2P_{3}\)-free graphs

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Complexity of finding maximum regular induced subgraphs with prescribed degree

Cites Work

• Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
• On distance-3 matchings and induced matchings
• Satgraphs and independent domination. I
• On the inapproximability of independent domination in \(2P_3\)-free perfect graphs
• Parameterized complexity of finding regular induced subgraphs
• The parameterized complexity of the induced matching problem
• On diameters and radii of bridged graphs
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Computing independent sets in graphs with large girth
• Some simplified NP-complete graph problems
• Subgraph isomorphism, matching relational structures and maximal cliques
• Induced matchings
• Induced matchings in asteroidal triple-free graphs
• Induced matchings in intersection graphs.
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• On the approximability of the maximum induced matching problem
• On maximum induced matchings in bipartite graphs
• Large \(2P_ 3\)-free graphs with bounded degree
• New results on induced matchings
• Maximum \(k\)-regular induced subgraphs
• A New Algorithm for Generating All the Maximal Independent Sets
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Independent Sets in Asteroidal Triple-Free Graphs
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
• Fast Exponential Algorithms for Maximum r-Regular Induced Subgraph Problems
• Independent Sets of Maximum Weight in Apple-Free Graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item