Algorithms for unipolar and generalized split graphs

DOI10.1016/j.dam.2013.08.011zbMath1300.05251MaRDI QIDQ741738

Elaine M. Eschen, Xiaoqiang Wang

Publication date: 12 September 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.08.011

zbMATH Keywords

split graph; minimal triangulation; efficient dominating set; perfect code; clique-split graph; generalized split graph; unipolar graph

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

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.)

05C17: Perfect graphs

Related Items

Solving Partition Problems Almost Always Requires Pushing Many Vertices Around, On efficient domination for some classes of \(H\)-free chordal graphs, On efficient domination for some classes of \(H\)-free chordal graphs, Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs, Recognition of unipolar and generalised split graphs, Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs, Efficient domination for classes of \(P_6\)-free graphs, Monopolar graphs: complexity of computing classical graph parameters, Weighted Efficient Domination for $P_5$-Free and $P_6$-Free Graphs, Weighted Efficient Domination for $$P_6$$ -Free and for $$P_5$$ -Free 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
• List monopolar partitions of claw-free graphs
• Recognizing line-polar bipartite graphs in time \(O(n)\)
• Solving partition problems with colour-bipartitions
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
• The strong perfect graph theorem
• The weighted perfect domination problem
• Polarity of chordal graphs
• A forbidden subgraph characterization of line-polar bipartite graphs
• About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
• Regular codes in regular graphs are difficult
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• Clique partitions, graph compression and speeding-up algorithms
• Weighted independent perfect domination on cocomparability graphs
• Polar permutation graphs are polynomial-time recognisable
• Linear time solvable optimization problems on graphs of bounded clique-width
• Incidence matrices and interval graphs
• Recognizing Polar Planar Graphs Using New Results for Monopolarity
• Line-Polar Graphs: Characterization and Recognition
• Easy problems for tree-decomposable graphs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Algorithmic Aspects of Vertex Elimination on Graphs
• Almost all Berge Graphs are Perfect
• Coloring the Maximal Cliques of Graphs
• A wide-range algorithm for minimal triangulation from an arbitrary ordering
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Polar cographs