On the complexity of the independent set problem in triangle graphs
From MaRDI portal
Publication:2275391
DOI10.1016/j.disc.2011.04.001zbMath1223.05215OpenAlexW2091196599WikidataQ57387734 ScholiaQ57387734MaRDI QIDQ2275391
Yury L. Orlovich, Gerd Finke, Jacek Błażewicz, Valery S. Gordon, Alexandre Dolgui
Publication date: 8 August 2011
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2011.04.001
Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
On equistable, split, CIS, and related classes of graphs ⋮ Equistable simplicial, very well-covered, and line graphs ⋮ Short proofs on the structure of general partition, equistable and triangle graphs ⋮ Algorithm to find a maximum 2-packing set in a cactus ⋮ Characterization of general position sets and its applications to cographs and bipartite graphs ⋮ 1-Triangle graphs and perfect neighborhood sets ⋮ Strong cliques and equistability of EPT graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Stability in CAN-free graphs
- Polar graphs and maximal independent sets
- Maximum independent sets in subclasses of \(P_{5}\)-free graphs
- Some results on graphs without long induced paths
- On maximal independent sets of vertices in claw-free graphs
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Complement reducible graphs
- Computing independent sets in graphs with large girth
- The independent neighbourhood number of a graph
- Scheduling jobs within time windows on identical parallel machines: New model and algorithms
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Independent sets in extensions of 2\(K_{2}\)-free graphs
- On the approximability of an interval scheduling problem
- Polynomially solvable cases for the maximum stable set problem
- On graphs whose maximal cliques and stable sets intersect
- A characterization and hereditary properties for partition graphs
- Bipartite bihypergraphs: a survey and new results
- Some Parameters on Neighborhood Number of A Graph
- An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
- On graphs with polynomially solvable maximum-weight clique problem
- The maximum independent set problem for cubic planar graphs
- Two-Processor Scheduling with Start-Times and Deadlines
- Maximum weighted independent sets on transitive graphs and applications
- Graph Classes: A Survey
- 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
- Some covering concepts in graphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- 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
- Graph-Theoretic Concepts in Computer Science
