Labeled cuts in graphs

DOI10.1016/J.TCS.2016.07.040MaRDI QIDQ313962zbMATH OpenOpenAlexFDO

Authors Lenwood S. Heath, V. S. Anil Kumar, Madhav V. Marathe, Tridib Dutta

Publication date 12 September 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2016.07.040

zbMATH Keywords

minimum cutregular languageslabeled graphs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25) Connectivity (05C40) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Recommendations

• Efficient Algorithms for the Label Cut Problems
• Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem
• Approximation and hardness results for label cut and related problems
• Approximation and Hardness Results for Label Cut and Related Problems
• Approximating minimum label \(s\)-\(t\) cut via linear programming

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1263226 (Why is no real title available?)
• scientific article; zbMATH DE number 1445322 (Why is no real title available?)
• Approximate strong separation with application in fractional graph coloring and preemptive scheduling.
• Approximation algorithms and hardness results for labeled connectivity problems
• Approximation and Hardness Results for Label Cut and Related Problems
• Connectivity and inference problems for temporal networks
• Finding Regular Simple Paths in Graph Databases
• Formal-Language-Constrained Path Problems
• On the minimum label spanning tree problem
• Regular path queries with constraints

Cited in

(8)

• Minimum label \(s\)-\(t\) cut has large integrality gaps
• How to Cut a Graph into Many Pieces
• Approximating minimum label \(s\)-\(t\) cut via linear programming
• Approximation and hardness results for label cut and related problems
• Maximum reachability preserved graph cut
• Efficient heuristics for the minimum labeling global cut problem
• The label cut problem with respect to path length and label frequency
• Approximation and Hardness Results for Label Cut and Related Problems

This page was built for publication: Labeled cuts in graphs

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