A minimization version of a directed subgraph homeomorphism problem

DOI10.1007/s00186-008-0259-0zbMath1161.90006OpenAlexW1987556067MaRDI QIDQ1014308

Janina A. Brenner, Jan C. van der Veen, Sándor P. Fekete

Publication date: 27 April 2009

Published in: Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00186-008-0259-0

zbMATH Keywords

NP-completenessapproximation algorithmsreconfigurable computingtopological minorhost graphsubgraph homeomorphismdata flow graphacyclic directed pattern graphminimal height

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic scheduling theory in operations research (90B35) Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• An approach to the subgraph homeomorphism problem
• The complexity of minimizing wire lengths in VLSI layouts
• The directed subgraph homeomorphism problem
• Topological subgraphs in graphs of large girth
• Large Topological Cliques in Graphs Without a 4-Cycle
• The subgraph homeomorphism problem
• The complexity of satisfiability problems
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: A minimization version of a directed subgraph homeomorphism problem