Maximum regular induced subgraphs in \(2P_3\)-free graphs
type: Item
instance of: scholarly article
title: Maximum regular induced subgraphs in \(2P_3\)-free graphs
zbMATH Open document ID: 1252.68155
author: Vadim Lozin
author: Raffaele Mosca
published in: Theoretical Computer Science
publication date: 2012-11-27T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 6110697
zbMATH Keywords: independent set
zbMATH Keywords: clique
zbMATH Keywords: induced matching
zbMATH Keywords: regular induced subgraph
zbMATH Keywords: polynomial-time algorithm
zbMATH Keywords: \(2P_{3}\)-free graphs
MaRDI profile type: Publication
full work available at URL: j.tcs.2012.06.014
OpenAlex ID: W1988197393
cites work: Polynomial algorithm for finding the largest independent sets in graphs without forks
cites work: Subgraph isomorphism, matching relational structures and maximal cliques
cites work: Q3145799
cites work: Independent Sets of Maximum Weight in Apple-Free Graphs
cites work: On distance-3 matchings and induced matchings
cites work: Independent Sets in Asteroidal Triple-Free Graphs
cites work: Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
cites work: Induced matchings
cites work: Induced matchings in intersection graphs.
cites work: Maximum \(k\)-regular induced subgraphs
cites work: Induced matchings in asteroidal triple-free graphs
cites work: Large \(2P_ 3\)-free graphs with bounded degree
cites work: On the approximability of the maximum induced matching problem
cites work: On diameters and radii of bridged graphs
cites work: Independence and irredundance in \(k\)-regular graphs
cites work: Some simplified NP-complete graph problems
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: Q4198056
cites work: New results on induced matchings
cites work: Q3216686
cites work: Fast Exponential Algorithms for Maximum r-Regular Induced Subgraph Problems
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
cites work: 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
cites work: On maximum induced matchings in bipartite graphs
cites work: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
cites work: Independent sets in extensions of 2\(K_{2}\)-free graphs
cites work: On maximal independent sets of vertices in claw-free graphs
cites work: Computing independent sets in graphs with large girth
cites work: The parameterized complexity of the induced matching problem
cites work: Parameterized complexity of finding regular induced subgraphs
cites work: A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
cites work: On the inapproximability of independent domination in \(2P_3\)-free perfect graphs
cites work: Q4770411
cites work: Q4871056
cites work: Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
cites work: A New Algorithm for Generating All the Maximal Independent Sets
cites work: Q4944970
cites work: Satgraphs and independent domination. I
DOI: 10.1016/J.TCS.2012.06.014
description: scientific article; zbMATH DE number 6110697