Algorithms for unipolar and generalized split graphs

DOI10.1016/j.dam.2013.08.011zbMath1300.05251OpenAlexW1970348285MaRDI 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 graphminimal triangulationefficient dominating setperfect codeclique-split graphgeneralized split graphunipolar graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) 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) Perfect graphs (05C17)

Related Items (10)

Weighted Efficient Domination for $$P_6$$ -Free and for $$P_5$$ -Free Graphs ⋮ Monopolar graphs: complexity of computing classical graph parameters ⋮ Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs ⋮ Weighted Efficient Domination for $P_5$-Free and $P_6$-Free Graphs ⋮ Recognition of unipolar and generalised split graphs ⋮ Efficient domination for classes of \(P_6\)-free graphs ⋮ Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs ⋮ On efficient domination for some classes of \(H\)-free chordal graphs ⋮ On efficient domination for some classes of \(H\)-free chordal graphs ⋮ Solving Partition Problems Almost Always Requires Pushing Many Vertices Around

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

This page was built for publication: Algorithms for unipolar and generalized split graphs