Algorithms for unipolar and generalized split graphs
From MaRDI portal
split graphminimal triangulationefficient dominating setperfect codeclique-split graphgeneralized split graphunipolar graph
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Perfect graphs (05C17)
Recommendations
Cites work
- scientific article; zbMATH DE number 436064 (Why is no real title available?)
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3977053 (Why is no real title available?)
- scientific article; zbMATH DE number 4085682 (Why is no real title available?)
- scientific article; zbMATH DE number 91051 (Why is no real title available?)
- scientific article; zbMATH DE number 3632548 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1305489 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 1156657 (Why is no real title available?)
- scientific article; zbMATH DE number 975419 (Why is no real title available?)
- A forbidden subgraph characterization of line-polar bipartite graphs
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- A wide-range algorithm for minimal triangulation from an arbitrary ordering
- About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Almost all Berge Graphs are Perfect
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Clique partitions, graph compression and speeding-up algorithms
- Coloring the Maximal Cliques of Graphs
- 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
- Easy problems for tree-decomposable graphs
- Graph theory with applications
- Incidence matrices and interval graphs
- Line-Polar Graphs: Characterization and Recognition
- Linear time solvable optimization problems on graphs of bounded clique-width
- List monopolar partitions of claw-free graphs
- Perfect codes and independent dominating sets
- Polar cographs
- Polar permutation graphs are polynomial-time recognisable
- Polarity of chordal graphs
- Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
- Recognizing line-polar bipartite graphs in time \(O(n)\)
- Recognizing polar planar graphs using new results for monopolarity
- Regular codes in regular graphs are difficult
- Solving partition problems with colour-bipartitions
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- The strong perfect graph theorem
- The weighted perfect domination problem
- Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
- Weighted independent perfect domination on cocomparability graphs
Cited in
(14)- Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs
- Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
- Weighted efficient domination for \(P_6\)-free and for \(P_5\)-free graphs
- scientific article; zbMATH DE number 1696523 (Why is no real title available?)
- Recognition of unipolar and generalised split graphs
- Solving partition problems almost always requires pushing many vertices around
- On efficient domination for some classes of \(H\)-free chordal graphs
- Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
- On efficient domination for some classes of \(H\)-free chordal graphs
- Weighted efficient domination for \(P_5\)-free and \(P_6\)-free graphs
- On two variants of split graphs: 2-unipolar graph and \(k\)-probe-split graph
- Monopolar graphs: complexity of computing classical graph parameters
- An algorithmic characterization of splitting signed graph
- Efficient domination for classes of \(P_6\)-free graphs
This page was built for publication: Algorithms for unipolar and generalized split graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q741738)
