Fabian Lipp, M. Sc.

2020

1.
Kaufmann, M., Kratochvil, J., Lipp, F., Montecchiani, F., Raftopoulou, C., Valtr, P.: The Stub Resolution of 1-Planar Graphs. In: Rahman, M.S., Sadakane, K., und Sung, W.-K. (hrsg.) WALCOM: Algorithms and Computation. S. 170–182. Springer (2020).
[ Abstract ] [ BibTeX ] [ URL ]
 
The resolution of a drawing plays a crucial role when defining criteria for its quality. In the past, grid resolution, edge-length resolution, angular resolution and crossing resolution have been investigated. In this paper, we investigate the stub resolution, a recently introduced criterion for nonplanar drawings. A crossed edge is divided into parts, called stubs, which should not be too short for the sake of readability. Thus, the stub resolution of a drawing is defined as the minimum ratio between the length of a stub and the length of the entire edge, over all the edges of the drawing. We consider 1-planar graphs and we explore scenarios in which near optimal stub resolution, i.e. arbitrarily close to \\($\$\)\backslashfrac\1\\2\\\($\$\), can be obtained in drawings with zero, one, or two bends per edge, as well as further resolution criteria, such as angular and crossing resolution. In particular, our main contributions are as follows: (i) Every 1-planar graph with independent crossing edges has a straight-line drawing with near optimal stub resolution; (ii) Every 1-planar graph has a 1-bend drawing with near optimal stub resolution.
@inproceedings{10.1007/978-3-030-39881-1_15, abstract = {The resolution of a drawing plays a crucial role when defining criteria for its quality. In the past, grid resolution, edge-length resolution, angular resolution and crossing resolution have been investigated. In this paper, we investigate the stub resolution, a recently introduced criterion for nonplanar drawings. A crossed edge is divided into parts, called stubs, which should not be too short for the sake of readability. Thus, the stub resolution of a drawing is defined as the minimum ratio between the length of a stub and the length of the entire edge, over all the edges of the drawing. We consider 1-planar graphs and we explore scenarios in which near optimal stub resolution, i.e. arbitrarily close to {\$}{\$}{\backslash}frac{\{}1{\}}{\{}2{\}}{\$}{\$}, can be obtained in drawings with zero, one, or two bends per edge, as well as further resolution criteria, such as angular and crossing resolution. In particular, our main contributions are as follows: (i) Every 1-planar graph with independent crossing edges has a straight-line drawing with near optimal stub resolution; (ii) Every 1-planar graph has a 1-bend drawing with near optimal stub resolution.}, author = {Kaufmann, Michael and Kratochvil, Jan and Lipp, Fabian and Montecchiani, Fabrizio and Raftopoulou, Chrysanthi and Valtr, Pavel}, booktitle = {WALCOM: Algorithms and Computation}, editor = {Rahman, M. Sohel and Sadakane, Kunihiko and Sung, Wing-Kin}, keywords = {1-planar graph-drawing myown resolution stub}, pages = {170--182}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {The Stub Resolution of 1-Planar Graphs}, volume = 12049, year = 2020 }

2.
Furdek, M., Natalino, C., Lipp, F., Hock, D., Di Giglio, A., Schiano, M.: Machine Learning for Optical Network Security Monitoring: A Practical Perspective. Journal of Lightwave Technology. 38, 2860–2871 (2020).
[ BibTeX ] [ URL ]
 
@article{furdek2020machine, author = {Furdek, Marija and Natalino, Carlos and Lipp, Fabian and Hock, David and Di Giglio, Andrea and Schiano, Marco}, journal = {Journal of Lightwave Technology}, keywords = {myown}, number = 11, pages = {2860--2871}, publisher = {IEEE}, title = {Machine Learning for Optical Network Security Monitoring: A Practical Perspective}, volume = 38, year = 2020 }

2019

1.
Chaplick, S., Lipp, F., Wolff, A., Zink, J.: Compact drawings of 1-planar graphs with right-angle crossings and few bends. Comput. Geom. 84, 50–68 (2019).
[ BibTeX ] [ URL ]
 
@article{journals/comgeo/ChaplickLWZ19, author = {Chaplick, Steven and Lipp, Fabian and Wolff, Alexander and Zink, Johannes}, journal = {Comput. Geom.}, keywords = {myown}, pages = {50-68}, title = {Compact drawings of 1-planar graphs with right-angle crossings and few bends.}, volume = 84, year = 2019 }

2.
Kalmbach, P., Hock, D., Lipp, F., Kellerer, W., Blenk, A.: NOracle: Who is communicating with whom in my network?. SIGCOMM Posters and Demos. S. 48–50. ACM (2019).
[ BibTeX ] [ URL ]
 
@inproceedings{conf/sigcomm/KalmbachHLKB19, author = {Kalmbach, Patrick and Hock, David and Lipp, Fabian and Kellerer, Wolfgang and Blenk, Andreas}, booktitle = {SIGCOMM Posters and Demos}, crossref = {conf/sigcomm/2019p}, keywords = {myown}, pages = {48-50}, publisher = {ACM}, title = {NOracle: Who is communicating with whom in my network?}, year = 2019 }

2018

1.
Chaplick, S., Lipp, F., Wolff, A., Zink, J.: 1-Bend RAC Drawings of NIC-Planar Graphs in Quadratic Area. In: Korman, M. und Mulzer, W. (hrsg.) Proc. 34th Europ. Workshop Comput. Geom. (EuroCG’18). S. 28:1– (2018).
[ BibTeX ] [ URL ]
 
@inproceedings{clwz-1brac-EuroCG18, author = {Chaplick, Steven and Lipp, Fabian and Wolff, Alexander and Zink, Johannes}, booktitle = {Proc. 34th Europ. Workshop Comput. Geom. (EuroCG'18)}, editor = {Korman, Matias and Mulzer, Wolfgang}, keywords = {myown}, pages = {28:1--6}, title = {1-Bend RAC Drawings of NIC-Planar Graphs in Quadratic Area}, year = 2018 }

2.
Kaufmann, M., Kratochvíl, J., Lipp, F., Montecchiani, F., Raftopoulou, C.N., Valtr, P.: Bounded Stub Resolution for Some Maximal 1-Planar Graphs. In: Panda, B.S. und Goswami, P.P. (hrsg.) CALDAM. S. 214–220. Springer (2018).
[ BibTeX ] [ URL ]
 
@inproceedings{conf/caldam/0001KLMRV18, author = {Kaufmann, Michael and Kratochvíl, Jan and Lipp, Fabian and Montecchiani, Fabrizio and Raftopoulou, Chrysanthi N. and Valtr, Pavel}, booktitle = {CALDAM}, crossref = {conf/caldam/2018}, editor = {Panda, B. S. and Goswami, Partha P.}, keywords = {myown}, pages = {214-220}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Bounded Stub Resolution for Some Maximal 1-Planar Graphs.}, volume = 10743, year = 2018 }

3.
Chaplick, S., Lipp, F., Wolff, A., Zink, J.: Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends. In: Biedl, T.C. und Kerren, A. (hrsg.) Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Barcelona, Spain, September 26-28, 2018, Proceedings. S. 137–151. Springer (2018).
[ Abstract ] [ BibTeX ] [ URL ]
 
We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is 1-planar if every edge is crossed at most once. A 1-planar drawing is IC-planar if no two pairs of crossing edges share a vertex. A 1-planar drawing is NIC-planar if no two pairs of crossing edges share two vertices. We study the relations of these beyond-planar graph classes to right-angle crossing (RAC) graphs that admit compact drawings on the grid with few bends. We present four drawing algorithms that preserve the given embeddings. First, we show that every \($n$\)-vertex NIC-planar graph admits a NIC-planar RAC drawing with at most one bend per edge on a grid of size \($O(n) O(n)$\). Then, we show that every \($n$\)-vertex 1-planar graph admits a 1-planar RAC drawing with at most two bends per edge on a grid of size \($O(n^3) O(n^3)$\). Finally, we make two known algorithms embedding-preserving; for drawing 1-planar RAC graphs with at most one bend per edge and for drawing IC-planar RAC graphs straight-line.
@inproceedings{conf/gd/ChaplickLWZ18, abstract = {We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is 1-planar if every edge is crossed at most once. A 1-planar drawing is IC-planar if no two pairs of crossing edges share a vertex. A 1-planar drawing is NIC-planar if no two pairs of crossing edges share two vertices. We study the relations of these beyond-planar graph classes to right-angle crossing (RAC) graphs that admit compact drawings on the grid with few bends. We present four drawing algorithms that preserve the given embeddings. First, we show that every $n$-vertex NIC-planar graph admits a NIC-planar RAC drawing with at most one bend per edge on a grid of size $O(n) O(n)$. Then, we show that every $n$-vertex 1-planar graph admits a 1-planar RAC drawing with at most two bends per edge on a grid of size $O(n^3) O(n^3)$. Finally, we make two known algorithms embedding-preserving; for drawing 1-planar RAC graphs with at most one bend per edge and for drawing IC-planar RAC graphs straight-line.}, author = {Chaplick, Steven and Lipp, Fabian and Wolff, Alexander and Zink, Johannes}, booktitle = {Graph Drawing and Network Visualization - 26th International Symposium, {GD} 2018, Barcelona, Spain, September 26-28, 2018, Proceedings}, editor = {Biedl, Therese C. and Kerren, Andreas}, keywords = {myown}, pages = {137--151}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends.}, volume = 11282, year = 2018 }

4.
van Dijk, T.C., Lipp, F., Markfelder, P., Wolff, A.: Computing Storyline Visualizations with Few Block Crossings. In: Frati, F. und Ma, K.-L. (hrsg.) Proc. 25th Int. Sympos. Graph Drawing Network Vis. (GD’17). S. 365–378. Springer-Verlag (2018).
[ BibTeX ] [ URL ]
 
@inproceedings{dlmw-csvfbc-GD2017, author = {van Dijk, Thomas C. and Lipp, Fabian and Markfelder, Peter and Wolff, Alexander}, booktitle = {Proc. 25th Int. Sympos. Graph Drawing Network Vis. (GD'17)}, editor = {Frati, Fabrizio and Ma, Kwan-Liu}, keywords = {myown}, pages = {365--378}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Computing Storyline Visualizations with Few Block Crossings}, volume = 10692, year = 2018 }

2017

1.
van Dijk, T.C., Fink, M., Fischer, N., Lipp, F., Markfelder, P., Ravsky, A., Suri, S., Wolff, A.: Block Crossings in Storyline Visualizations. Journal of Graph Algorithms & Applications. 21, 873–913 (2017).
[ Abstract ] [ BibTeX ] [ URL ]
 
Storyline visualizations help visualize encounters of the characters in a story over time. Each character is represented by an x-monotone curve that goes from left to right visualizing progression of time. A meeting is represented by having the characters that participate in the meeting run close together for some time. In order to keep the visual complexity low, rather than just minimizing pairwise crossings of curves, we propose to count block crossings, that is, pairs of intersecting bundles of lines. In a block crossing, two blocks of parallel lines intersect each other, which is less distracting than the same number of individual crossings being spread over the drawing. In this paper, we show that minimizing the number of block crossings is NP-hard, even if all meetings are of size 2. For this special case, we present a greedy heuristic, which we evaluate experimentally. We show that the general case is fixed-parameter tractable. Our main results is a constant-factor approximation algorithm for meetings of bounded size. The algorithm is based on (approximately) solving a hyperedge deletion problem on hypergraphs that may be of independent interest.
@article{dfflmrsw-bcisv-JGAA17, abstract = {Storyline visualizations help visualize encounters of the characters in a story over time. Each character is represented by an x-monotone curve that goes from left to right visualizing progression of time. A meeting is represented by having the characters that participate in the meeting run close together for some time. In order to keep the visual complexity low, rather than just minimizing pairwise crossings of curves, we propose to count block crossings, that is, pairs of intersecting bundles of lines. In a block crossing, two blocks of parallel lines intersect each other, which is less distracting than the same number of individual crossings being spread over the drawing. In this paper, we show that minimizing the number of block crossings is NP-hard, even if all meetings are of size 2. For this special case, we present a greedy heuristic, which we evaluate experimentally. We show that the general case is fixed-parameter tractable. Our main results is a constant-factor approximation algorithm for meetings of bounded size. The algorithm is based on (approximately) solving a hyperedge deletion problem on hypergraphs that may be of independent interest.}, author = {van Dijk, Thomas C. and Fink, Martin and Fischer, Norbert and Lipp, Fabian and Markfelder, Peter and Ravsky, Alexander and Suri, Subhash and Wolff, Alexander}, editor = {Hu, Yifan and Nöllenburg, Martin}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {experiments myown sat storylines}, number = 5, pages = {873--913}, title = {Block Crossings in Storyline Visualizations}, volume = 21, year = 2017 }

2.
Chaplick, S., Fleszar, K., Lipp, F., Ravsky, A., Verbitsky, O., Wolff, A.: The Complexity of Drawing Graphs on Few Lines and Few Planes. In: Ellen, F., Kolokolova, A., und Sack, J.-R. (hrsg.) Proc. Algorithms Data Struct. Symp. (WADS’17). S. 265–276. Springer-Verlag (2017).
[ Abstract ] [ BibTeX ] [ URL ]
 
It is well known that any graph admits a crossing-free straight-line drawing in  \\($\$\)backslashmathbb R ^3\\($\$\) and that any planar graph admits the same even in  \\($\$\)backslashmathbb R ^2\\($\$\) . For a graph G and \\($\$\)d backslashin \backslash\2,3\backslash\\\($\$\) , let \\($\$\)backslashrho ^1\_d(G)\\($\$\) denote the minimum number of lines in \\($\$\)backslashmathbb R ^d\\($\$\) that together can cover all edges of a drawing of G. For \\($\$\)d=2\\($\$\) , G must be planar. We investigate the complexity of computing these parameters and obtain the following hardness and algorithmic results.
@inbook{cflrvw-cdgfl-WADS17, abstract = {It is well known that any graph admits a crossing-free straight-line drawing in  {\$}{\$}{\backslash}mathbb {\{}R{\}} ^3{\$}{\$} and that any planar graph admits the same even in  {\$}{\$}{\backslash}mathbb {\{}R{\}} ^2{\$}{\$} . For a graph G and {\$}{\$}d {\backslash}in {\backslash}{\{}2,3{\backslash}{\}}{\$}{\$} , let {\$}{\$}{\backslash}rho ^1{\_}d(G){\$}{\$} denote the minimum number of lines in {\$}{\$}{\backslash}mathbb {\{}R{\}} ^d{\$}{\$} that together can cover all edges of a drawing of G. For {\$}{\$}d=2{\$}{\$} , G must be planar. We investigate the complexity of computing these parameters and obtain the following hardness and algorithmic results.}, author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander}, booktitle = {Proc. Algorithms Data Struct. Symp. (WADS'17)}, editor = {Ellen, Faith and Kolokolova, Antonina and Sack, Jörg-Rüdiger}, keywords = {"affinity myown number"}, pages = {265--276}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {The Complexity of Drawing Graphs on Few Lines and Few Planes}, volume = 10389, year = 2017 }

2016

1.
Chaplick, S., Lipp, F., Park, J.-W., Wolff, A.: Obstructing Visibilities with One Obstacle. In: Hu, Y. und Nöllenburg, M. (hrsg.) Proceedings of the 24th Int. Symp. on Graph Drawing & Network Visualization. S. 295–308. Springer (2016).
[ BibTeX ] [ URL ]
 
@inproceedings{clpw-obwoo-GD16, author = {Chaplick, Steven and Lipp, Fabian and Park, Ji{-}Won and Wolff, Alexander}, booktitle = {Proceedings of the 24th Int. Symp. on Graph Drawing & Network Visualization}, editor = {Hu, Yifan and Nöllenburg, Martin}, keywords = {myown}, pages = {295-308}, publisher = {Springer}, title = {Obstructing Visibilities with One Obstacle}, volume = 9801, year = 2016 }

2.
Lipp, F., Wolff, A., Zink, J.: Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition. Algorithms. 9, 53 (2016).
[ Abstract ] [ BibTeX ] [ URL ]
 
The force-directed paradigm is one of the few generic approaches to drawing graphs. Since force-directed algorithms can be extended easily, they are used frequently. Most of these algorithms are, however, quite slow on large graphs, as they compute a quadratic number of forces in each iteration. We give a new algorithm that takes only O ( m + n log n ) time per iteration when laying out a graph with n vertices and m edges. Our algorithm approximates the true forces using the so-called well-separated pair decomposition. We perform experiments on a large number of graphs and show that we can strongly reduce the runtime, even on graphs with less than a hundred vertices, without a significant influence on the quality of the drawings (in terms of the number of crossings and deviation in edge lengths).
@article{lwz-ffdgd-algorithms16, abstract = {The force-directed paradigm is one of the few generic approaches to drawing graphs. Since force-directed algorithms can be extended easily, they are used frequently. Most of these algorithms are, however, quite slow on large graphs, as they compute a quadratic number of forces in each iteration. We give a new algorithm that takes only O ( m + n log n ) time per iteration when laying out a graph with n vertices and m edges. Our algorithm approximates the true forces using the so-called well-separated pair decomposition. We perform experiments on a large number of graphs and show that we can strongly reduce the runtime, even on graphs with less than a hundred vertices, without a significant influence on the quality of the drawings (in terms of the number of crossings and deviation in edge lengths).}, author = {Lipp, Fabian and Wolff, Alexander and Zink, Johannes}, journal = {Algorithms}, keywords = {experiments force-directed graph-drawing myown well-separated-pair-decomposition}, number = 3, pages = 53, title = {Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition}, volume = 9, year = 2016 }

3.
van Dijk, T.C., Fink, M., Fischer, N., Lipp, F., Markfelder, P., Ravsky, A., Suri, S., Wolff, A.: Block Crossings in Storyline Visualizations. In: Hu, Y. und Nöllenburg, M. (hrsg.) Proc. 24th Int. Sympos. Graph Drawing Network Vis. (GD’16). S. 382–398. Springer-Verlag (2016).
[ BibTeX ] [ URL ]
 
@inproceedings{DBLP:journals/corr/Dijk0FLMRSW16, author = {van Dijk, Thomas C. and Fink, Martin and Fischer, Norbert and Lipp, Fabian and Markfelder, Peter and Ravsky, Alexander and Suri, Subhash and Wolff, Alexander}, booktitle = {Proc. 24th Int. Sympos. Graph Drawing Network Vis. (GD'16)}, editor = {Hu, Yifan and Nöllenburg, Martin}, keywords = {myown}, note = {Best paper award.}, pages = {382-398}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Block Crossings in Storyline Visualizations}, volume = 9801, year = 2016 }

4.
Chaplick, S., Fleszar, K., Lipp, F., Ravsky, A., Verbitsky, O., Wolff, A.: Drawing Graphs on Few Lines and Few Planes. In: Hu, Y. und Nöllenburg, M. (hrsg.) Proc. 24th Int. Sympos. Graph Drawing Network Vis. (GD’16). S. 166–180. Springer (2016).
[ BibTeX ] [ URL ]
 
@inproceedings{cflrvw-dgoflafp-GD16, author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander}, booktitle = {Proc. 24th Int. Sympos. Graph Drawing Network Vis. (GD'16)}, editor = {Hu, Yifan and Nöllenburg, Martin}, keywords = {myown}, pages = {166-180}, publisher = {Springer}, title = {Drawing Graphs on Few Lines and Few Planes}, volume = 9801, year = 2016 }

5.
Angelini, P., Chaplick, S., Cornelsen, S., Lozzo, G.D., Battista, G.D., Eades, P., Kindermann, P., Kratochvíl, J., Lipp, F., Rutter, I.: Simultaneous Orthogonal Planarity. In: Hu, Y. und Nöllenburg, M. (hrsg.) Proc. 24th Int. Sympos. Graph Drawing Network Vis. (GD’16). S. 532–545. Springer (2016).
[ BibTeX ] [ URL ]
 
@inproceedings{acclbekklr-sop-GD16, author = {Angelini, Patrizio and Chaplick, Steven and Cornelsen, Sabine and Lozzo, Giordano Da and Battista, Giuseppe Di and Eades, Peter and Kindermann, Philipp and Kratochv{í}l, Jan and Lipp, Fabian and Rutter, Ignaz}, booktitle = {Proc. 24th Int. Sympos. Graph Drawing Network Vis. (GD'16)}, editor = {Hu, Yifan and Nöllenburg, Martin}, keywords = {myown}, pages = {532-545}, publisher = {Springer}, title = {Simultaneous Orthogonal Planarity}, volume = 9801, year = 2016 }

2015

1.
Chaplick, S., Kindermann, P., Lipp, F., Wolff, A.: Solving Optimization Problems on Orthogonal Ray Graphs. Proc. Japan. Conf. Discrete Comput. Geom. Graphs (JCDCG\($^2$\)’15). S. 2 pp (2015).
[ BibTeX ]
 
@inproceedings{cklw-sopor-JCDCGG15, author = {Chaplick, Steven and Kindermann, Philipp and Lipp, Fabian and Wolff, Alexander}, booktitle = {Proc. Japan. Conf. Discrete Comput. Geom. Graphs (JCDCG$^2$'15)}, keywords = {myown}, note = {Abstract}, pages = {2 pp.}, title = {Solving Optimization Problems on Orthogonal Ray Graphs}, year = 2015 }

2.
Lipp, F., Wolff, A., Zink, J.: Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition. In: Di Giacomo, E. und Lubiw, A. (hrsg.) Graph Drawing and Network Visualization. S. 52–59. Springer International Publishing (2015).
[ BibTeX ] [ URL ]
 
@incollection{noKey, author = {Lipp, Fabian and Wolff, Alexander and Zink, Johannes}, booktitle = {Graph Drawing and Network Visualization}, editor = {Di Giacomo, Emilio and Lubiw, Anna}, keywords = {force-directed myown wspd}, pages = {52-59}, publisher = {Springer International Publishing}, series = {Lecture Notes in Computer Science}, title = {Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition}, volume = 9411, year = 2015 }

2014

1.
Lipp, F.: Boundary Labeling for Annotations in Texts, http://www1.informatik.uni-wuerzburg.de/pub/theses/2014-lipp-master.pdf, (2014).
[ BibTeX ] [ URL ]
 
@mastersthesis{lipp2014boundary, author = {Lipp, Fabian}, keywords = {boundary labeling myown}, title = {Boundary Labeling for Annotations in Texts}, type = {master thesis}, year = 2014 }

2.
Kindermann, P., Lipp, F., Wolff, A.: Luatodonotes: Boundary Labeling for Annotations in Texts. In: Duncan, C. und Symvonis, A. (hrsg.) Proc. 22nd Int. Sympos. Graph Drawing (GD’14). S. 76–88. Springer-Verlag (2014).
[ BibTeX ] [ URL ]
 
@inproceedings{klw-lblat-GD14, author = {Kindermann, Philipp and Lipp, Fabian and Wolff, Alexander}, booktitle = {Proc. 22nd Int. Sympos. Graph Drawing (GD'14)}, editor = {Duncan, Christian and Symvonis, Antonios}, keywords = {annotations boundary labeling myown texts}, pages = {76-88}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Luatodonotes: Boundary Labeling for Annotations in Texts}, volume = 8871, year = 2014 }

2012

1.
Lipp, F.: Computing the Flip Distance of Triangulations, http://www1.informatik.uni-wuerzburg.de/pub/theses/2012-lipp-bachelor.pdf, (2012).
[ BibTeX ] [ URL ]
 
@mastersthesis{lipp2012computing, author = {Lipp, Fabian}, keywords = {distance flip myown triangulations}, title = {Computing the Flip Distance of Triangulations}, type = {bachelor thesis}, year = 2012 }

2.
Fleszar, K., Glaßer, C., Lipp, F., Reitwießner, C., Witek, M.: Structural Complexity of Multiobjective NP Search Problems. In: Fernández-Baca, D. (hrsg.) LATIN 2012: Theoretical Informatics. S. 338–349. Springer Berlin Heidelberg (2012).
[ Abstract ] [ BibTeX ] [ URL ]
 
An NP search problem is a multivalued function that maps instances to polynomially length-bounded solutions such that the validity of solutions is testable in polynomial time. NPMV_g denotes the class of these functions. There are at least two computational tasks associated with an NP search problem: (i) Find out whether a solution exists. (ii) Compute an arbitrary solution. Further computational tasks arise in settings with multiple objectives, for example: (iii) Compute a solution that is minimal w.r.t. the first objective, while the second objective does not exceed some budget. Each such computational task defines a class of multivalued functions. We systematically investigate these classes and their relation to traditional complexity classes and classes of multivalued functions, like NP or max·P. For multiobjective problems, some classes of computational tasks turn out to be equivalent to the function class NPMV_g , some to the class of decision problems NP, and some to a seemingly new class that includes both NPMV_g and NP. Under the assumption that certain exponential time classes are different, we show that there are computational tasks of multiobjective problems (more precisely functions in NPMV_g) that are Turing-inequivalent to any set.
@incollection{noKey, abstract = {An NP search problem is a multivalued function that maps instances to polynomially length-bounded solutions such that the validity of solutions is testable in polynomial time. NPMV_g denotes the class of these functions. There are at least two computational tasks associated with an NP search problem: (i) Find out whether a solution exists. (ii) Compute an arbitrary solution. Further computational tasks arise in settings with multiple objectives, for example: (iii) Compute a solution that is minimal w.r.t. the first objective, while the second objective does not exceed some budget. Each such computational task defines a class of multivalued functions. We systematically investigate these classes and their relation to traditional complexity classes and classes of multivalued functions, like NP or max·P. For multiobjective problems, some classes of computational tasks turn out to be equivalent to the function class NPMV_g , some to the class of decision problems NP, and some to a seemingly new class that includes both NPMV_g and NP. Under the assumption that certain exponential time classes are different, we show that there are computational tasks of multiobjective problems (more precisely functions in NPMV_g) that are Turing-inequivalent to any set.}, author = {Fleszar, Krzysztof and Glaßer, Christian and Lipp, Fabian and Reitwießner, Christian and Witek, Maximilian}, booktitle = {LATIN 2012: Theoretical Informatics}, editor = {Fernández-Baca, David}, keywords = {complexity multiobjective myown np search structural}, pages = {338-349}, publisher = {Springer Berlin Heidelberg}, series = {Lecture Notes in Computer Science}, title = {Structural Complexity of Multiobjective NP Search Problems}, volume = 7256, year = 2012 }