Complexity and algorithms for recognizing polar and monopolar graphs

DOI10.1016/j.tcs.2014.01.032zbMath1283.05219OpenAlexW2003128536MaRDI QIDQ2437850

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 complexitypolar graphplanar graphmonopolar 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)

Related Items

Monopolar graphs: complexity of computing classical graph parameters ⋮ Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs ⋮ Minimal obstructions to 2-polar cographs ⋮ Unnamed Item ⋮ Minimal obstructions to \(( \infty , k )\)-polarity in cographs ⋮ Solving Partition Problems Almost Always Requires Pushing Many Vertices Around

Cites Work

• Unnamed Item
• Recognizing line-polar bipartite graphs in time \(O(n)\)
• 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
• The NP-completeness of (1,r)-subcolorability of cubic graphs
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• Polar permutation graphs are polynomial-time recognisable
• Linear time solvable optimization problems on graphs of bounded clique-width
• Recognizing Polar Planar Graphs Using New Results for Monopolarity
• Line-Polar Graphs: Characterization and Recognition
• Easy problems for tree-decomposable graphs
• Minimum-weight triangulation is NP-hard
• On graphs with polynomially solvable maximum-weight clique problem
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the Polarity and Monopolarity of Graphs
• A Computing Procedure for Quantification Theory
• Polar cographs
• Hard tiling problems with simple tiles