Complexity and algorithms for recognizing polar and monopolar graphs

DOI10.1016/J.TCS.2014.01.032MaRDI QIDQ2437850zbMATH OpenOpenAlexFDO

Authors Van Bang Le, Ragnar Nevries

Publication date 13 March 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.01.032

zbMATH Keywords

computational complexitymonopolar graphplanar graphpolar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) 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)

Recommendations

• Recognizing polar planar graphs using new results for monopolarity
• On the Polarity and Monopolarity of Graphs
• Polar cographs
• About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs
• Line-Polar Graphs: Characterization and Recognition

Cites work

• A Computing Procedure for Quantification Theory
• A forbidden subgraph characterization of line-polar bipartite graphs
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs
• Easy problems for tree-decomposable graphs
• Hard tiling problems with simple tiles
• scientific article; zbMATH DE number 3977053 (Why is no real title available?)
• Line-Polar Graphs: Characterization and Recognition
• Linear time solvable optimization problems on graphs of bounded clique-width
• Minimum-weight triangulation is NP-hard
• On graphs with polynomially solvable maximum-weight clique problem
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the Polarity and Monopolarity of Graphs
• Polar cographs
• Polar permutation graphs are polynomial-time recognisable
• Polarity of chordal graphs
• Recognizing line-polar bipartite graphs in time \(O(n)\)
• Recognizing polar planar graphs using new results for monopolarity
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The NP-completeness of (1,r)-subcolorability of cubic graphs
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard

Cited in

(18)

• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Minimal obstructions to ( , k )-polarity in cographs
• Towards detecting structural branching and cyclicity in graphs: a polynomial-based approach
• Minimal obstructions to 2-polar cographs
• Monopolar graphs: complexity of computing classical graph parameters
• Recognizing polar planar graphs using new results for monopolarity
• Line-Polar Graphs: Characterization and Recognition
• Solving partition problems almost always requires pushing many vertices around
• Uniquely monopolar-partitionable block graphs
• Solving partition problems almost always requires pushing many vertices around
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• On the Polarity and Monopolarity of Graphs
• Recognizing hyperelliptic graphs in polynomial time
• On two variants of split graphs: 2-unipolar graph and k-probe-split graph
• Faster algorithms for graph monopolarity
• Algorithms for unipolar and generalized split graphs
• Solving partition problems with colour-bipartitions
• Polar graphs and maximal independent sets

This page was built for publication: Complexity and algorithms for recognizing polar and monopolar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437850)