Deleting vertices to bound path length

DOI10.1109/12.312117MaRDI QIDQ4419764zbMATH OpenOpenAlexFDO

Authors Doowon Paik, Sudhakar M. Reddy, Sartaj Sahni

Publication date 1994

Published in IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/8feb58d33bccab4464ba82566003428166640834

zbMATH Keywords

weighted directed acyclic graphs

Mathematics Subject Classification ID

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

Recommendations

• Edge Weight Reduction Problems in Directed Acyclic Graphs
• Finding paths and deleting edges in directed acyclic graphs
• Vertex splitting in dags and applications to partial scan designs and lossy circuits
• On a DAG partitioning problem
• A quartic kernel for pathwidth-one vertex deletion

Cited in

(9)

• Finding paths and deleting edges in directed acyclic graphs
• Using edge contractions and vertex deletions to reduce the independence number and the clique number
• Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
• Hardness of vertex deletion and project scheduling
• Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
• Vertex splitting in dags and applications to partial scan designs and lossy circuits
• Reducing graph parameters by contractions and deletions
• On blockers and transversals of maximum independent sets in co-comparability graphs
• A randomized rounding approach for DAG edge deletion

This page was built for publication: Deleting vertices to bound path length

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