Labeled cuts in graphs

DOI10.1016/j.tcs.2016.07.040zbMath1350.68138OpenAlexW2516171751MaRDI QIDQ313962

Lenwood S. Heath, Madhav V. Marathe, V. S. Anil Kumar, Tridib K. 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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Regular path queries with constraints
• Approximate strong separation with application in fractional graph coloring and preemptive scheduling.
• On the minimum label spanning tree problem
• Approximation algorithms and hardness results for labeled connectivity problems
• Approximation and Hardness Results for Label Cut and Related Problems
• Formal-Language-Constrained Path Problems
• Finding Regular Simple Paths in Graph Databases
• Connectivity and inference problems for temporal networks

This page was built for publication: Labeled cuts in graphs