Algorithms for unipolar and generalized split graphs
type: Item
instance of: scholarly article
title: Algorithms for unipolar and generalized split graphs
zbMATH Open document ID: 1300.05251
author: Elaine M. Eschen
author: Xiaoqiang Wang
published in: Discrete Applied Mathematics
publication date: 2014-09-12T00:00:00Z
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C17
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6344083
zbMATH Keywords: split graph
zbMATH Keywords: clique-split graph
zbMATH Keywords: unipolar graph
zbMATH Keywords: generalized split graph
zbMATH Keywords: minimal triangulation
zbMATH Keywords: perfect code
zbMATH Keywords: efficient dominating set
MaRDI profile type: Publication
full work available at URL: j.dam.2013.08.011
OpenAlex ID: W1970348285
cites work: Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
cites work: Q3139841
cites work: Easy problems for tree-decomposable graphs
cites work: A linear-time algorithm for testing the truth of certain quantified Boolean formulas
cites work: Coloring the Maximal Cliques of Graphs
cites work: Q3815323
cites work: Q4252378
cites work: A wide-range algorithm for minimal triangulation from an arbitrary ordering
cites work: Q3097395
cites work: Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
cites work: Weighted independent perfect domination on cocomparability graphs
cites work: About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs
cites work: The strong perfect graph theorem
cites work: Line-Polar Graphs: Characterization and Recognition
cites work: List monopolar partitions of claw-free graphs
cites work: Solving partition problems with colour-bipartitions
cites work: The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Polar permutation graphs are polynomial-time recognisable
cites work: Polarity of chordal graphs
cites work: Recognizing line-polar bipartite graphs in time \(O(n)\)
cites work: Polar cographs
cites work: Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
cites work: Clique partitions, graph compression and speeding-up algorithms
cites work: Q4017197
cites work: Q4193514
cites work: Incidence matrices and interval graphs
cites work: Q4198056
cites work: Q3328583
cites work: Corrigendum to our paper ''The ellipsoid method and its consequences in combinatorial optimization''
cites work: Q4368728
cites work: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
cites work: A forbidden subgraph characterization of line-polar bipartite graphs
cites work: Perfect codes and independent dominating sets
cites work: Regular codes in regular graphs are difficult
cites work: Recognizing Polar Planar Graphs Using New Results for Monopolarity
cites work: Q5284096
cites work: Almost all Berge Graphs are Perfect
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: Q4390693
cites work: Q3743346
cites work: The weighted perfect domination problem
DOI: 10.1016/J.DAM.2013.08.011
description: scientific article; zbMATH DE number 6344083