Hardness and structural results for half-squares of restricted tree convex bipartite graphs

DOI10.1007/s00453-018-0440-7zbMath1434.68365arXiv1804.05793OpenAlexW2952421273WikidataQ129979146 ScholiaQ129979146MaRDI QIDQ5919674

Hoàng-Oanh Le, Van Bang Le

Publication date: 17 October 2019

Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1804.05793

zbMATH Keywords

computational complexitygraph algorithmNP-hardnessgraph classeshalf-square

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Map graphs having witnesses of large girth ⋮ Weighted 2-sections and hypergraph reconstruction ⋮ Beyond Helly graphs: the diameter problem on absolute retracts ⋮ Recognizing map graphs of bounded treewidth ⋮ Unnamed Item ⋮ Hardness and structural results for half-squares of restricted tree convex bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Feedback vertex sets on restricted bipartite graphs
• On the complete width and edge clique cover problems
• Characterizations of strongly chordal graphs
• A characterization of totally balanced hypergraphs
• Computing roots of graphs is hard
• Efficient graph representations
• Linear-time recognition of circular-arc graphs
• FO model checking on map graphs
• Incidence matrices and interval graphs
• Approximation Algorithms for Independent Sets in Map Graphs
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Bipartite roots of graphs
• Map graphs
• Doubly Lexical Orderings of Matrices
• The NP-Completeness of Some Edge-Partition Problems
• Covering edges by cliques with regard to keyword conflicts and intersection graphs
• Topics in Intersection Graph Theory
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Restricted Bipartite Graphs: Comparison and Hardness Results
• Linear-Time Recognition of Map Graphs with Outerplanar Witness
• A Characterization of Comparability Graphs and of Interval Graphs
• Hardness and structural results for half-squares of restricted tree convex bipartite graphs

This page was built for publication: Hardness and structural results for half-squares of restricted tree convex bipartite graphs