While it is very reasonable to use a multigraph consisting of multiple edges between vertices to represent various relationships, the multigraph has not drawn much attention in research. To visualize such a multigraph...While it is very reasonable to use a multigraph consisting of multiple edges between vertices to represent various relationships, the multigraph has not drawn much attention in research. To visualize such a multigraph, a clear layout representing a global structure is of great importance, and interactive visual analysis which allows the multiple edges to be adjusted in appropriate ways for detailed presentation is also essential. A novel interactive two-phase approach to visualizing and exploring multigraph is proposed. The approach consists of two phases： the first phase improves the previous popular works on force-directed methods to produce a brief drawing for the aggregation graph of the input multigraph, while the second phase proposes two interactive strategies, the magnifier model and the thematic-oriented subgraph model. The former highlights the internal details of an aggregation edge which is selected interactively by user, and draws the details in a magnifying view by cubic Bezier curves; the latter highlights only the thematic subgraph consisting of the selected multiple edges that the user concerns. The efficiency of the proposed approach is demonstrated with a real-world multigraph dataset and how it is used effectively is discussed for various potential applications.展开更多
We analyze a common feature of p-Kemeny AGGregation（p-KAGG） and p-One-Sided Crossing Minimization（p-OSCM） to provide new insights and findings of interest to both the graph drawing community and the social choice ...We analyze a common feature of p-Kemeny AGGregation（p-KAGG） and p-One-Sided Crossing Minimization（p-OSCM） to provide new insights and findings of interest to both the graph drawing community and the social choice community. We obtain parameterized subexponential-time algorithms for p-KAGG—a problem in social choice theory—and for p-OSCM—a problem in graph drawing. These algorithms run in time O＊（2O（√k log k））,where k is the parameter, and significantly improve the previous best algorithms with running times O.1.403k/and O.1.4656k/, respectively. We also study natural ＂above-guarantee＂ versions of these problems and show them to be fixed parameter tractable. In fact, we show that the above-guarantee versions of these problems are equivalent to a weighted variant of p-directed feedback arc set. Our results for the above-guarantee version of p-KAGG reveal an interesting contrast. We show that when the number of ＂votes＂ in the input to p-KAGG is odd the above guarantee version can still be solved in time O＊（2O（√k log k））, while if it is even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails（equivalently, unless FPT D M[1]）.展开更多
Deep space networks,satellite networks,ad hoc networks,and the Internet can be modeled as DTNs(Delay Tolerant Networks).As a fundamental problem,the maximum flow problem is of vital importance for routing and service ...Deep space networks,satellite networks,ad hoc networks,and the Internet can be modeled as DTNs(Delay Tolerant Networks).As a fundamental problem,the maximum flow problem is of vital importance for routing and service scheduling in networks.However,there exists no permanent end-to-end path since the topology and the characteristics of links are time-variant,resulting in a crucial maximum flow problem in DTNs.In this paper,we focus on the single-source-single-sink maximum flow problem of buffer-limited DTNs,followed by a valid algorithm to solve it.First,the BTAG(Buffer-limited Time Aggregated Graph)is constructed for modeling the buffer-limited DTN.Then,on the basis of BTAG,the two-way cache transfer series and the relevant transfer rules are designed,and thus a BTAG-based maximum flow algorithm is proposed to solve the maximum flow problem in buffer-limited DTNs.Finally,a numerical example is given to demonstrate the effectiveness of the proposed algorithm.展开更多
基金supported by the National Natural Science Fundation of China(61103081)
文摘While it is very reasonable to use a multigraph consisting of multiple edges between vertices to represent various relationships, the multigraph has not drawn much attention in research. To visualize such a multigraph, a clear layout representing a global structure is of great importance, and interactive visual analysis which allows the multiple edges to be adjusted in appropriate ways for detailed presentation is also essential. A novel interactive two-phase approach to visualizing and exploring multigraph is proposed. The approach consists of two phases： the first phase improves the previous popular works on force-directed methods to produce a brief drawing for the aggregation graph of the input multigraph, while the second phase proposes two interactive strategies, the magnifier model and the thematic-oriented subgraph model. The former highlights the internal details of an aggregation edge which is selected interactively by user, and draws the details in a magnifying view by cubic Bezier curves; the latter highlights only the thematic subgraph consisting of the selected multiple edges that the user concerns. The efficiency of the proposed approach is demonstrated with a real-world multigraph dataset and how it is used effectively is discussed for various potential applications.
基金supported by a GermanNorwegian PPP grantsupported by the Indo-German Max Planck Center for Computer Science (IMPECS)
文摘We analyze a common feature of p-Kemeny AGGregation（p-KAGG） and p-One-Sided Crossing Minimization（p-OSCM） to provide new insights and findings of interest to both the graph drawing community and the social choice community. We obtain parameterized subexponential-time algorithms for p-KAGG—a problem in social choice theory—and for p-OSCM—a problem in graph drawing. These algorithms run in time O＊（2O（√k log k））,where k is the parameter, and significantly improve the previous best algorithms with running times O.1.403k/and O.1.4656k/, respectively. We also study natural ＂above-guarantee＂ versions of these problems and show them to be fixed parameter tractable. In fact, we show that the above-guarantee versions of these problems are equivalent to a weighted variant of p-directed feedback arc set. Our results for the above-guarantee version of p-KAGG reveal an interesting contrast. We show that when the number of ＂votes＂ in the input to p-KAGG is odd the above guarantee version can still be solved in time O＊（2O（√k log k））, while if it is even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails（equivalently, unless FPT D M[1]）.
基金supported by the National Science Foundation(Nos.91338115,61231008)National S&T Major Project(No.2015ZX03002006)+2 种基金the Fundamental Research Funds for the Central Universities(Nos.WRYB142208,JB140117)Shanghai Aerospace Science and Technology Innovation Fund(No.201454)the 111 Project(No.B08038).
文摘Deep space networks,satellite networks,ad hoc networks,and the Internet can be modeled as DTNs(Delay Tolerant Networks).As a fundamental problem,the maximum flow problem is of vital importance for routing and service scheduling in networks.However,there exists no permanent end-to-end path since the topology and the characteristics of links are time-variant,resulting in a crucial maximum flow problem in DTNs.In this paper,we focus on the single-source-single-sink maximum flow problem of buffer-limited DTNs,followed by a valid algorithm to solve it.First,the BTAG(Buffer-limited Time Aggregated Graph)is constructed for modeling the buffer-limited DTN.Then,on the basis of BTAG,the two-way cache transfer series and the relevant transfer rules are designed,and thus a BTAG-based maximum flow algorithm is proposed to solve the maximum flow problem in buffer-limited DTNs.Finally,a numerical example is given to demonstrate the effectiveness of the proposed algorithm.
