Bounded degree interval sandwich problems

DOI10.1007/PL00009277zbMATH Open0934.68070MaRDI QIDQ1293876FDOQ1293876

Ron Shamir, Haim Kaplan

Publication date: 3 April 2000

Published in: Algorithmica (Search for Journal in Brave)

Recommendations

• On intervalizing \(k\)-colored graphs for DNA physical mapping
• Intervalizing \(k\)-colored graphs
• The hardness of intervalizing four colored caterpillars
• Complexity and algorithms for graph and hypergraph sandwich problems

zbMATH Keywords

interval sandwichintervalizing colored graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Cited In (15)

• Exact algorithms for intervalizing coloured graphs
• The graph sandwich problem for \(P_4\)-sparse graphs
• Title not available (Why is that?)
• The graph sandwich problem for 1-join composition is NP-complete
• The homogeneous set sandwich problem
• On decision and optimization (\(k\),\(l\))-graph sandwich problems
• Near-optimal solutions for the generalized max-controlled set problem
• The external constraint 4 nonempty part sandwich problem
• Complexity classification of some edge modification problems
• The pair completion algorithm for the homogeneous set sandwich problem
• Improved Lower Bounds for Graph Embedding Problems
• The sandwich problem for cutsets: clique cutset, \(k\)-star cutset
• A sandwich with segment convexity
• An improved derandomized approximation algorithm for the max-controlled set problem
• On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs

This page was built for publication: Bounded degree interval sandwich problems

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