Exact Computation of Minimum Feedback Vertex Sets with Relational Algebra

• Autorzy: Berghammer R. , Fronk A.
• Języki publikacji: EN

Abstrakty

EN

A feedback vertex set of a graph is a subset of vertices containing at least one vertex from every cycle of the graph. Given a directed graph by its adjacency relation, we develop a relational algorithm for computing a feedback vertex set of minimum size. In combination with a BDD-implementation of relations, it allows to exactly solve this NP-hard problem for medium-sized graphs.

Słowa kluczowe

EN

directed graphs; feedback vertex sets; elementary chordless cycles; relational algebra; RELVIEW tool

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 70, nr 4
• Strony: 301--316
• Opis fizyczny: wykr., bibliogr. 20 poz.

Twórcy

autor

Berghammer R.

autor

Fronk A.

• Institute of Computer Science and Applied Mathematics, University of Kiel, D-24098 Kiel, Germany,

Bibliografia

• [1] Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.: Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference, SIAM Journal on Computing, (27), 1998, 942-959.
• [2] Baumgarten, B.: Petri-Netze: Grundlagen und Anwendungen, BI-Wissenschafts-Verlag, 1990.
• [3] Behnke, R., Berghammer, R., Meyer, E., Schneider, P.: RELVIEW - A system for calculating with relations and relational programming, Proceedings of the 1st International Conference on Fundamental Approaches to Software Engineering (E. Astesiano, Ed.), Lecture Notes in Computer Science 1382, Springer, 1996.
• [4] Berghammer, R., Hoffmann, T.: Modeling sequences within the RELVIEW system, Journal of Universal Computer Science, 7(2), 2001, 107-123.
• [5] Berghammer, R., Leoniuk, B., Milanese, U.: Implementation of relational algebra using binary decision diagrams, Proceedings of the 6th International Workshop on Relational Methods in Computer Science (RelMiCS6) (H. de Swart, Ed.), Lecture Notes in Computer Science 2561, Springer, 2002.
• [6] Berghammer, R., Rusinowska, A., de Swart H.: Graphs, RELVIEW, and Coalition Formation. In preparation.
• [7] Desel, J., Esparza, J.: Free Choice Petri Nets, vol. 40 of Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, 1995.
• [8] Diaz, M., Richard, J., Courvoisier, M.: A Note on Minimal and Quasi-minimal Essential Sets in Complex Directed Graphs, IEEE Transactions on Circuit Theory, (19), 1972, 512-513.
• [9] Esparza, J., Silva, M.: Circuits, Handles, Bridges and Nets, Advances in Petri Nets (G. Rozenberg, Ed.), Lecture Notes in Computer Science 483, Springer, 1990.
• [10] Even, G., Naor, J., Schieber, B., Sudan, M.: Approximating Minimum Feedback Sets and Multi-cuts in Directed Graphs, Proceedings of the 4th Conference on Integer Programming and Combinatorial Optimization (E. Balas, J. Clausen, Eds.), Lecture Notes in Computer Science 920, Springer, 1995.
• [11] Fronk, A.: Using relation algebra for the analysis of Petri nets in a CASE tool based approach, 2nd IEEE International Conference on Software Engineering and Formal Methods (SEFM), Beijing, IEEE, 2004.
• [12] Fronk, A., Pleumann, J., Schönlein, R., Szymanski, O.: KURE-Java, available via http://ls10-www.cs.uni-dortmund.de/index/php?id136, 2005.
• [13] Fronk, A., Schönlein, R.: RelClipse, available via http://ls10-www.cs.uni-dortmund.de/index/php?id137.
• [14] Hafna, V., Berman, P., Fujito, T.: A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem, SIAM Journal on Discrete Mathematics, (17), 1999, 289-297.
• [15] Karp, R.: Reducibility among combinatorial problems, Proceedings of a Symposium on the Complexity and Computer Computation (R. Miller, J. Thatcher, Eds.), Plenum Press, New York, 1972.
• [16] Kevorkian, A.: The Principal Maxmin Matrix Transversal Strategy, Journal on Mathematics and Operations Research, (4), 1979.
• [17] Leoniuk, B.: ROBDD-based implementation of relational algebra with applications, Ph.D. Thesis, Institut für Informatik und Praktische Mathematik, Universit¨at Kiel, 2001, In German.
• [18] Milanese, U.: On the implementation of a ROBDD-based tool for the manipulation and visualization of relations, Ph.D. Thesis, Institut für Informatik und Praktische Mathematik, Universit¨at Kiel, 2003, In German.
• [19] Schmidt, G., Ströhlein, T.: Relations and graphs, EATCS Monographs on Theoretical Computer Science, Spinger, 1993.
• [20] Seshu, S., Reed, M.: Linear Graphs and Electrical Networks, Addison-Wesley, 1961.