Vertex covering by paths on trees with its applications in machine translation

DOI10.1016/j.ipl.2005.09.006zbMath1184.68359OpenAlexW2058621291MaRDI QIDQ1045903

Dekang Lin, Zhipeng Cai, Guo-Hui Lin

Publication date: 18 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.09.006

zbMATH Keywords

algorithmscombinatorial problemsmachine translationvertex covering by paths

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Natural language processing (68T50)

Related Items (3)

Approximation for vertex cover in \(\beta\)-conflict graphs ⋮ Vertex cover in conflict graphs ⋮ Two fixed-parameter algorithms for vertex covering by paths on trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Approximation algorithms for combinatorial problems
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• Path covering problems and testing of printed circuits
• An Almost Linear-Time Algorithm for Graph Realization
• Approximation Algorithms for Several Graph Augmentation Problems
• Augmentation Problems
• On Path Cover Problems in Digraphs and Applications to Program Testing
• Biconnectivity approximations and graph carvings

This page was built for publication: Vertex covering by paths on trees with its applications in machine translation