Labeled cuts in graphs

DOI10.1016/J.TCS.2016.07.040zbMATH Open1350.68138OpenAlexW2516171751MaRDI QIDQ313962FDOQ313962

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the minimum label spanning tree problem
• Connectivity and inference problems for temporal networks
• Title not available (Why is that?)
• Regular path queries with constraints
• 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
• Formal-Language-Constrained Path Problems
• Finding Regular Simple Paths in Graph Databases
• Title not available (Why is that?)

Cited In (1)

• How to Cut a Graph into Many Pieces

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)