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

DOI10.1016/j.tcs.2012.06.014zbMath1252.68155OpenAlexW1988197393MaRDI 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 setpolynomial-time algorithmcliqueinduced matchingregular induced subgraph\(2P_{3}\)-free graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (11)

A sufficient condition to extend polynomial results for the maximum independent set problem ⋮ New results on independent sets in extensions of \(2K_2\)-free graphs ⋮ From matchings to independent sets ⋮ Complexity of finding maximum regular induced subgraphs with prescribed degree ⋮ Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time ⋮ On the maximum independent set problem in subclasses of subcubic graphs ⋮ On some hard and some tractable cases of the maximum acyclic matching problem ⋮ Sparse regular induced subgraphs in \(2P_3\)-free graphs ⋮ Graphs without large apples and the maximum weight independent set problem ⋮ Independent sets in \((P_4+P_4\),triangle)-free graphs ⋮ Moderately exponential time algorithms for the maximum induced matching problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Maximum regular induced subgraphs in \(2P_3\)-free graphs