A minimization version of a directed subgraph homeomorphism problem

DOI10.1007/S00186-008-0259-0MaRDI QIDQ1014308zbMATH OpenOpenAlexFDO

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

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

approximation algorithmsNP-completenessreconfigurable computingtopological minorhost graphdata flow graphacyclic directed pattern graphminimal heightsubgraph homeomorphism

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 19351
• Processor optimization for flow graphs
• An exact algorithm for subgraph homeomorphism
• The subgraph homeomorphism problem
• The interconnection problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• An approach to the subgraph homeomorphism problem
• Combinatorial optimization. Theory and algorithms.
• Large Topological Cliques in Graphs Without a 4-Cycle
• The complexity of minimizing wire lengths in VLSI layouts
• The complexity of satisfiability problems
• The directed subgraph homeomorphism problem
• The subgraph homeomorphism problem
• Topological subgraphs in graphs of large girth

Cited in

(2)

• scientific article; zbMATH DE number 5531978 (Why is no real title available?)
• Minimum 0-extension problems on directed metrics

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

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