Approximating the maximum clique minor and some subgraph homeomorphism problems
From MaRDI portal
Publication:1022596
DOI10.1016/j.tcs.2006.12.021zbMath1162.05342OpenAlexW1982718046MaRDI QIDQ1022596
Noga Alon, Andrzej Lingas, Martin Wahlen
Publication date: 22 June 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2006.12.021
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83) Approximation algorithms (68W25)
Related Items
Hadwiger Number of Graphs with Small Chordality, On the complexity of approximating the Hadwiger number, Connected matchings in chordal bipartite graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of subgraph isomorphism for classes of partial k-trees
- On approximating the longest path in a graph
- Lower bound of the Hadwiger number of graphs by their average degree
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- A partial k-arboretum of graphs with bounded treewidth
- Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Which problems have strongly exponential complexity?
- Graph minors. XIII: The disjoint paths problem
- Approximating the Longest Cycle Problem in Sparse Graphs
- An extremal function for contractions of graphs
- Finding paths and cycles of superpolylogarithmic length
- Graph minors. II. Algorithmic aspects of tree-width
- On Linear Time Minor Tests with Depth-First Search
- Color-coding
- Finding a Path of Superlogarithmic Length
- The approximation of maximum subgraph problems
- Approximating Maximum Clique by Removing Subgraphs
- The Pathwidth and Treewidth of Cographs
- Topological cliques in graphs II
- Sequential and parallel algorithms for embedding problems on classes of partial k-trees
- Algorithms and Data Structures
