On the complete width and edge clique cover problems

DOI10.1007/s10878-016-0106-9zbMath1393.05211arXiv1612.08057OpenAlexW2950324051MaRDI QIDQ721937

Sheng-Lung Peng, Van Bang Le

Publication date: 20 July 2018

Published in: Lecture Notes in Computer Science, Journal of Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

bipartite graphssplit graphsedge clique coverprobe graphscomplete width

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (5)

Fast constructive and improvement heuristics for edge clique covering ⋮ Unnamed Item ⋮ On the complete width and edge clique cover problems ⋮ Hardness and structural results for half-squares of restricted tree convex bipartite graphs ⋮ On some FPT problems without polynomial Turing compressions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of the algorithmic aspects of modular decomposition
• Block-graph width
• On the complete width and edge clique cover problems
• On probe permutation graphs
• Linear time algorithms on circular-arc graphs
• Linear recognition of pseudo-split graphs
• Graphs with no induced \(C_ 4\) and \(2K_ 2\)
• Algorithmic graph theory and perfect graphs
• Threshold graphs and related topics
• On edge perfectness and classes of bipartite graphs
• Characterizing and recognizing probe block graphs
• Clique Cover and Graph Separation: New Incompressibility Results
• Clique Covering of Graphs IV. Algorithms
• Known Algorithms for Edge Clique Cover are Probably Optimal
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Node-Deletion Problems on Bipartite Graphs
• The NP-Completeness of Some Edge-Partition Problems
• Covering edges by cliques with regard to keyword conflicts and intersection graphs
• Graph Classes: A Survey
• Data Reduction, Exact, and Heuristic Algorithms for Clique Cover
• Data reduction and exact algorithms for clique cover
• Parameterized Algorithms
• Difference graphs

This page was built for publication: On the complete width and edge clique cover problems